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

Bounds of Quantum Mixing Processes via Controlled Walks

Li, Shang

Published Apr 29, 2020• 0 citations
Publisher

Abstract

Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.

DOI
10.11575/prism/37751

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

Quantum Walks On Graphs

Dorit Aharonov, Andris Ambainis, Julia Kempe +1 more

We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.

arXiv:quant-ph/0012090•Dec 18, 2000•102 citations

Quantum walks on graphs

Dorit Aharonov, Andris Ambainis, Julia Kempe +1 more

We set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.

ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•652 citations

Quantum Searching on Markov Chains - The Complete Graph

Min-Ho Lee, Nark Nyul Choi, Gregor Tanner

We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.

Acta Physica Polonica A•Dec 1, 2021•3 citations

QUANTUM HITTING TIME ON THE COMPLETE GRAPH

Raqueline A. M. Santos, Renato Portugal

Quantum walks play an important role in the area of quantum algorithms. Many interesting problems can be reduced to searching marked states in a quantum Markov chain. In this context, the notion of quantum hitting time is very important, because it quantifies the running time of the algorithms. Markov chain-based algorithms are probabilistic, therefore the calculation of the success probability is also required in the analysis of the computational complexity. Using Szegedy's definition of quantum hitting time, which is a natural extension of the definition of the classical hitting time, we present analytical expressions for the hitting time and success probability of the quantum walk on the complete graph.

arXiv:0912.1217•International Journal of Quantum Information•Aug 1, 2010•24 citations

Bounds for mixing time of quantum walks on finite graphs

Vladislav Kargin

Several inequalities are proved for the mixing time of discrete-time quantum walks on finite graphs. The mixing time is defined differently than in Aharonov et al (2002 Proc. 33rd STOC ( 2001 ) (New York: ACM) pp 50–9 arXiv:quant-ph/0012090v2) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speedup in mixing over the classical counterparts. In addition, non-unitary quantum walks (i.e. walks with decoherence) are considered and a criterion for their convergence to the unique stationary distribution is derived.

arXiv:1004.0188•Journal of Physics A Mathematical and Theoretical•Jul 15, 2010•9 citations
Quantum mixing is a category of processes of reaching a stationary state when starting from a single initial vertex via quantum walks. In this thesis, we introduce the quantum mixing processes based on the framework of controlled quantum walks in [DH17a]. We first discuss why Szegedy's walks are not well-suited for the quantum mixing processes. We then show that the controlled quantum walk is a suitable framework for achieving a quadratic speed-up in the quantum mixing processes, because of its relationship with interpolated walks [KMOR16] and the phase estimation algorithm [CEMM98]. Accordingly, we give two definitions of quantum mixing times via controlled quantum walks: instant quantum mixing time and average quantum mixing time. We later prove the bounds of these two quantum mixing times on complete graphs. We also prove the upper bound of the average quantum mixing times on cycle graphs. To have clearer views on the bounds of instant and average quantum mixing times, we then discuss and present the simulations of quantum mixing processes, with four types of graphs (complete graphs, cycle graphs, 2-dimensional tori and dumbbell graphs) as examples. The simulations include the quantum mixing processes with the same ~θ (an important parameter in the controlled quantum walk operator) as in [DH17a], and the suitable range of ~θ that achieves the quadratic speed-up for different types of graphs. Inspired by the quantum search algorithm via controlled quantum walks in [DH17a], we adapt this algorithm to a new algorithm of quantum mixing, which generates samples from the stationary distribution of the Markov chain, with its runtime upper bounded by the quantum hitting time, which is quadratically faster than the classical hitting process.
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.
We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.
We set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.
We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.
Quantum walks play an important role in the area of quantum algorithms. Many interesting problems can be reduced to searching marked states in a quantum Markov chain. In this context, the notion of quantum hitting time is very important, because it quantifies the running time of the algorithms. Markov chain-based algorithms are probabilistic, therefore the calculation of the success probability is also required in the analysis of the computational complexity. Using Szegedy's definition of quantum hitting time, which is a natural extension of the definition of the classical hitting time, we present analytical expressions for the hitting time and success probability of the quantum walk on the complete graph.
Several inequalities are proved for the mixing time of discrete-time quantum walks on finite graphs. The mixing time is defined differently than in Aharonov et al (2002 Proc. 33rd STOC ( 2001 ) (New York: ACM) pp 50–9 arXiv:quant-ph/0012090v2) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speedup in mixing over the classical counterparts. In addition, non-unitary quantum walks (i.e. walks with decoherence) are considered and a criterion for their convergence to the unique stationary distribution is derived.