Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2001.06305 · Physical Review Letters

How Fast Do Quantum Walks Mix?

Shantanav Chakraborty, Kyle Luh, Jérémie Roland

Published Feb 3, 2020• 25 citations
arXivHTMLPDF

Abstract

The fundamental problem of sampling from the limiting distribution of quantum walks on networks, known as mixing, finds widespread applications in several areas of quantum information and computation. Of particular interest in most of these applications is the minimum time beyond which the instantaneous probability distribution of the quantum walk remains close to this limiting distribution, known as the "quantum mixing time". However, this quantity is only known for a handful of specific networks. In this Letter, we prove an upper bound on the quantum mixing time for almost all networks, i.e., the fraction of networks for which our bound holds, goes to one in the asymptotic limit. To this end, using several results in random matrix theory, we find the quantum mixing time of Erdös-Renyi random networks: networks of n nodes where each edge exists with probability p independently. For example, for dense random networks, where p is a constant, we show that the quantum mixing time is O(n^{3/2+o(1)}). In addition to opening avenues for the analytical study of quantum dynamics on random networks, our work could find applications beyond quantum information processing. Owing to the universality of Wigner random matrices, our results on the spectral properties of random graphs hold for general classes of random matrices that are ubiquitous in several areas of physics. In particular, our results could lead to novel insights into the equilibration times of isolated quantum systems defined by random Hamiltonians, a foundational problem in quantum statistical mechanics.

DOI
10.1103/physrevlett.124.050501

Related papers

Analog quantum algorithms for the mixing of Markov chains

Shantanav Chakraborty, Kyle Luh, Jérémie Roland

The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that, given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently, we provided an upper bound on the quantum mixing time for Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic, and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain.

arXiv:1904.11895•Physical Review A•Aug 25, 2020•21 citations

Characterizing the Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks

Matheus Guedes de Andrade, Franklin de Lima Marquezino, Daniel R. Figueiredo

Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.

•Jun 29, 2021•0 citations

Quantum speedup of classical mixing processes

Peter C. Richter

Most approximation algorithms for #$\mathit{P}$-complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution $\ensuremath{\pi}$ over a large set $\mathcal{S}$. This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain $P$ on $\mathcal{S}$ with stationary distribution $\ensuremath{\pi}$ is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of $P$, is $O({\ensuremath{\delta}}^{\ensuremath{-}1}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ as shown by Aldous, where $\ensuremath{\delta}$ is the spectral gap of $P$ and ${\ensuremath{\pi}}_{\ensuremath{\ast}}$ is the minimum value of $\ensuremath{\pi}$. A natural question is whether a speedup of this classical method to $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice ${\mathbb{Z}}_{n}^{d}$ is $O(nd\text{ }\text{log}\text{ }d)$, which is indeed $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ and is asymptotically no worse than the diameter of ${\mathbb{Z}}_{n}^{d}$ (the obvious lower bound) up to at most a logarithmic factor.

arXiv:quant-ph/0609204•Physical Review A•Oct 4, 2007•87 citations

Quantum Speedup for Sampling Random Spanning Trees

Simon Apers, Gao, Minbo, Zhengfeng Ji +1 more

We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.

Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Almost uniform sampling via quantum walks

Peter C. Richter

Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.

arXiv:quant-ph/0606202•New Journal of Physics•Mar 22, 2007•54 citations

Uniform Mixing of Quantum Walks and Association Schemes

Natalie Mullin

In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. \n \nThere are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. \n \nWe begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. \n \nNext we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. \n \nFinally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.

•Sep 26, 2013•3 citations
The fundamental problem of sampling from the limiting distribution of quantum walks on networks, known as mixing, finds widespread applications in several areas of quantum information and computation. Of particular interest in most of these applications is the minimum time beyond which the instantaneous probability distribution of the quantum walk remains close to this limiting distribution, known as the "quantum mixing time". However, this quantity is only known for a handful of specific networks. In this Letter, we prove an upper bound on the quantum mixing time for almost all networks, i.e., the fraction of networks for which our bound holds, goes to one in the asymptotic limit. To this end, using several results in random matrix theory, we find the quantum mixing time of Erdös-Renyi random networks: networks of n nodes where each edge exists with probability p independently. For example, for dense random networks, where p is a constant, we show that the quantum mixing time is O(n^{3/2+o(1)}). In addition to opening avenues for the analytical study of quantum dynamics on random networks, our work could find applications beyond quantum information processing. Owing to the universality of Wigner random matrices, our results on the spectral properties of random graphs hold for general classes of random matrices that are ubiquitous in several areas of physics. In particular, our results could lead to novel insights into the equilibration times of isolated quantum systems defined by random Hamiltonians, a foundational problem in quantum statistical mechanics.
The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that, given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently, we provided an upper bound on the quantum mixing time for Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic, and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain.
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.
Most approximation algorithms for #P\mathit{P}P-complete problems (e.g., evaluating the partition function of a monomer-dimer or ferromagnetic Ising system) work by reduction to the problem of approximate sampling from a distribution $\ensuremath{\pi}$ over a large set S\mathcal{S}S. This problem is solved using the Markov chain Monte Carlo method: a sparse, reversible Markov chain PPP on S\mathcal{S}S with stationary distribution $\ensuremath{\pi}$ is run to near equilibrium. The running time of this random walk algorithm, the so-called mixing time of PPP, is $O({\ensuremath{\delta}}^{\ensuremath{-}1}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ as shown by Aldous, where $\ensuremath{\delta}$ is the spectral gap of PPP and ${\ensuremath{\pi}}_{\ensuremath{\ast}}$ is the minimum value of $\ensuremath{\pi}$. A natural question is whether a speedup of this classical method to $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ is possible using quantum walks. We provide evidence for this possibility using quantum walks that decohere under repeated randomized measurements. We show that (i) decoherent quantum walks always mix, just like their classical counterparts, (ii) the mixing time is a robust quantity, essentially invariant under any smooth form of decoherence, and (iii) the mixing time of the decoherent quantum walk on a periodic lattice Znd{\mathbb{Z}}_{n}^{d}Znd​ is O(nd log d)O(nd\text{ }\text{log}\text{ }d)O(nd log d), which is indeed $O(\sqrt{{\ensuremath{\delta}}^{\ensuremath{-}1}}\text{ }\text{log}\text{ }1∕{\ensuremath{\pi}}_{\ensuremath{\ast}})$ and is asymptotically no worse than the diameter of Znd{\mathbb{Z}}_{n}^{d}Znd​ (the obvious lower bound) up to at most a logarithmic factor.
We present a quantum algorithm for sampling random spanning trees from a weighted graph in Õ(√{mn}) time, where n and m denote the number of vertices and edges, respectively. Our algorithm has sublinear runtime for dense graphs and achieves a quantum speedup over the best-known classical algorithm, which runs in Õ(m) time. The approach carefully combines, on one hand, a classical method based on "large-step" random walks for reduced mixing time and, on the other hand, quantum algorithmic techniques, including quantum graph sparsification and a sampling-without-replacement variant of Hamoudi’s multiple-state preparation. We also establish a matching lower bound, proving the optimality of our algorithm up to polylogarithmic factors. These results highlight the potential of quantum computing in accelerating fundamental graph sampling problems.
Many classical randomized algorithms (e.g. approximation algorithms for #P-complete problems) utilize the following random walk algorithm for almost uniform sampling from a state space S of cardinality N : run a symmetric ergodic Markov chain P on S for long enough to obtain a random state from within total variation distance of the uniform distribution over S . The running time of this algorithm, the so-called mixing time of P , is O (δ −1 (log N +log −1 )), where δ is the spectral gap of P . We present a natural quantum version of this algorithm based on repeated measurements of the quantum walk U t = e −i Pt . We show that it samples almost uniformly from S with logarithmic dependence on −1 just as the classical walk P does; previously, no such quantum walk algorithm was known. We then outline a framework for analysing its running time and formulate two plausible conjectures which together would imply that it runs in time O (δ −1/2 log N log −1 ) when P is the standard transition matrix of a constant-degree graph. We prove each conjecture for a subclass of Cayley graphs.
In recent years quantum algorithms have become a popular area of mathematical research. Farhi and Gutmann introduced the concept of a quantum walk in 1998. In this thesis we investigate mixing properties of continuous-time quantum walks from a mathematical perspective. We focus on the connections between mixing properties and association schemes. \n \nThere are three main goals of this thesis. Our primary goal is to develop the algebraic groundwork necessary to systematically study mixing properties of continuous-time quantum walks on regular graphs. Using these tools we achieve two additional goals: we construct new families of graphs that admit uniform mixing, and we prove that other families of graphs never admit uniform mixing. \n \nWe begin by introducing association schemes and continuous-time quantum walks. Within this framework we develop specific algebraic machinery to tackle the uniform mixing problem. Our main algebraic result shows that if a graph has an irrational eigenvalue, then its transition matrix has at least one transcendental coordinate at all nonzero times. \n \nNext we study algebraic varieties related to uniform mixing to determine information about the coordinates of the corresponding transition matrices. Combining this with our main algebraic result we prove that uniform mixing does not occur on even cycles or prime cycles. However, we show that the probability distribution of a quantum walk on a prime cycle gets arbitrarily close to uniform. \n \nFinally we consider uniform mixing on Cayley graphs of elementary abelian groups. We utilize graph quotients to connect the mixing properties of these graphs to Hamming graphs. This enables us to find new results about uniform mixing on Cayley graphs of certain elementary abelian groups.