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

Fast Mixing with Quantum Walks vs. Classical Processes

Simon Apers, Alain Sarlette, Francesco Ticozzi

Published Jan 1, 2017• 1 citation
OpenAlex

Abstract

Quantum walks have been linked to acceleration in various information processing tasks, and proposed as a possible model for quantum-enhanced behavior in biological systems.These links and acceleration claims have been made with various levels of detail.Here we consider discrete-time quantum walks, and focus on the task of mixing, i.e., distributing the state over a graph.Previous papers have observed that the so-called coined quantum walks can accelerate mixing on certain graphs with respect to the optimal classical Markov chain.We here show that the same speedup can be attained with a classical process, if a similar classical coin is added.We establish a precise correspondence between the mixing performance of quantum walks and such "lifted walks" for all (finite) graphs, and thereby improve known bounds on quantum walk mixing time.We conclude that the advantage of quantum walks with respect to classical processes is not in the mixing speed of the optimal design.However, a notable quantum advantage might reside in the fact that the mixing speed obtained with suboptimal designs, due to for instance limited graph knowledge, appears to be generically faster.

Related papers

Simulation of quantum walks and fast mixing with classical processes

Simon Apers, Alain Sarlette, Francesco Ticozzi

We compare discrete-time quantum walks on graphs to their natural classical equivalents, which we argue are lifted Markov chains (LMCs), that is, classical Markov chains with added memory. We show that LMCs can simulate the mixing behavior of any quantum walk, under a commonly satisfied invariance condition. This allows us to answer an open question on how the graph topology ultimately bounds a quantum walk's mixing performance, and that of any stochastic local evolution. The results highlight that speedups in mixing and transport phenomena are not necessarily diagnostic of quantum effects, although superdiffusive spreading is more prominent with quantum walks. The general simulating LMC construction may lead to large memory, yet we show that for the main graphs under study (i.e., lattices) this memory can be brought down to the same size employed in the quantum walks proposed in the literature.

arXiv:1712.01609•Physical Review A•Sep 20, 2018•16 citations

For every quantum walk there is a (classical) lifted Markov chain with faster mixing time

Danial Dervovic

Quantum walks on graphs have been shown in certain cases to mix quadratically faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. Here, we construct a lifted Markov chain on a graph with $n^2 D(G)$ vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph $G$ with $n$ vertices, where $D(G)$ is the diameter of $G$. Moreover, the mixing time of this chain is $D(G)$ timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in $n$. As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).

arXiv:1712.02318•Dec 6, 2017•3 citations

Bounds of Quantum Mixing Processes via Controlled Walks

Li, Shang

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.

•Apr 29, 2020•0 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 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

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 walks have been linked to acceleration in various information processing tasks, and proposed as a possible model for quantum-enhanced behavior in biological systems.These links and acceleration claims have been made with various levels of detail.Here we consider discrete-time quantum walks, and focus on the task of mixing, i.e., distributing the state over a graph.Previous papers have observed that the so-called coined quantum walks can accelerate mixing on certain graphs with respect to the optimal classical Markov chain.We here show that the same speedup can be attained with a classical process, if a similar classical coin is added.We establish a precise correspondence between the mixing performance of quantum walks and such "lifted walks" for all (finite) graphs, and thereby improve known bounds on quantum walk mixing time.We conclude that the advantage of quantum walks with respect to classical processes is not in the mixing speed of the optimal design.However, a notable quantum advantage might reside in the fact that the mixing speed obtained with suboptimal designs, due to for instance limited graph knowledge, appears to be generically faster.
We compare discrete-time quantum walks on graphs to their natural classical equivalents, which we argue are lifted Markov chains (LMCs), that is, classical Markov chains with added memory. We show that LMCs can simulate the mixing behavior of any quantum walk, under a commonly satisfied invariance condition. This allows us to answer an open question on how the graph topology ultimately bounds a quantum walk's mixing performance, and that of any stochastic local evolution. The results highlight that speedups in mixing and transport phenomena are not necessarily diagnostic of quantum effects, although superdiffusive spreading is more prominent with quantum walks. The general simulating LMC construction may lead to large memory, yet we show that for the main graphs under study (i.e., lattices) this memory can be brought down to the same size employed in the quantum walks proposed in the literature.
Quantum walks on graphs have been shown in certain cases to mix quadratically faster than their classical counterparts. Lifted Markov chains, consisting of a Markov chain on an extended state space which is projected back down to the original state space, also show considerable speedups in mixing time. Here, we construct a lifted Markov chain on a graph with n2D(G)n^2 D(G)n2D(G) vertices that mixes exactly to the average mixing distribution of a quantum walk on the graph GGG with nnn vertices, where D(G)D(G)D(G) is the diameter of GGG. Moreover, the mixing time of this chain is D(G)D(G)D(G) timesteps, and we prove that computing the transition probabilities for the lifted chain takes time polynomial in nnn. As an immediate consequence, for every quantum walk there is a lifted Markov chain with a faster mixing time that is polynomial-time computable, as the quantum mixing time is trivially lower bounded by the graph diameter. The result is based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).
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.
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.
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.