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

Quantum walks : speed limits on mixing and fast-forwarding classical walks

Simon Apers

Published Jan 1, 2019• 1 citation
OpenAlex

Abstract

The theme that underlies this thesis is the mutualist relation between classical walks and quantum walks on graphs, the latter being a promising algorithmic component of future quantum computers.We study both sides of this coin.On the one side we prove how classical walks can simulate quantum walks.This allows the use of folklore bounds on the behavior of classical walks to study speed limits on quantum walks, a question which had long evaded progress.On the other side, we prove how quantum walks can be used to speed up the behavior of a large class of classical walks.This leads to a new quantum algorithm which we call quantum walk fast-forwarding.We show that this algorithm allows to naturally speed up classical walk algorithms for search and property testing on graphs.The work is theoretical and mathematical, and supposed to be relevant for quantum computers that should some day exist.I feel proud of this work, and am indebted to many people.Foremost I must thank my supervisor Alain Sarlette, you have been the best supervisor I could wish for, if only for learning me that no-go proofs are traffic diversions rather than dead ends.

Related papers

Fast Mixing with Quantum Walks vs. Classical Processes

Simon Apers, Alain Sarlette, Francesco Ticozzi

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.

•Jan 1, 2017•0 citations

Quantum Fast-Forwarding: Markov Chains and Graph Property Testing

Simon Apers, Alain Sarlette

We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with $P$ the Markov chain transition matrix and $D = \sqrt{P\circ P^T}$ its discriminant matrix ($D=P$ if $P$ is symmetric), we construct a quantum walk algorithm that for any quantum state $|v\rangle$ and integer $t$ returns a quantum state $ε$-close to the state $D^t|v\rangle/\|D^t|v\rangle\|$. The algorithm uses $O\Big(\|D^t|v\rangle\|^{-1}\sqrt{t\log(ε\|D^t|v\rangle\|)^{-1}}\Big)$ expected quantum walk steps and $O(\|D^t|v\rangle\|^{-1})$ expected reflections around $|v\rangle$. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of $s$-$t$ connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.

arXiv:1804.02321•Apr 6, 2018•12 citations

Quantum fast-forwarding : Markov chains and graph property testing

Simon Apers, Alain Sarlette

We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = root P omicron P-T its discriminant matrix (D = P if P is symmetric), we construct a quantum walk algorithm that for any quantum state vertical bar v > and integer t returns a quantum state epsilon-close to the state D-t vertical bar v > /parallel to D-t vertical bar v > parallel to. The algorithm uses O(parallel to D-t vertical bar v > parallel to(-1) root t log(epsilon parallel to D-t vertical bar v > parallel to(-1)) expected quantum walk steps and O(parallel to D-t vertical bar v > parallel to(-1)) expected reflections around vertical bar v >. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.

•Jan 1, 2019•0 citations

Quantum fast-forwarding: Markov chains and graph property testing

Simon Apers, Alain Scarlet

We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = \sqrt{P\circ P^T} its discriminant matrix (D=P if P is symmetric), we construct a quantum walk algorithm that for any quantum state |v> and integer t returns a quantum state \epsilon-close to the state D^t|v>/\|D^t|v>. The algorithm uses O(|D^t|v>|^{-1}\sqrt{t\log(\epsilon\|D^t|v>})^{-1}}) expected quantum walk steps and O(\|D^t|v>|^{-1}) expected reflections around |v>. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.

Quantum Information and Computation•Mar 1, 2019•31 citations

Quantum walks, the discrete wave equation and Chebyshev polynomials

Simon Apers, Laurent Miclo

A quantum walk is the quantum analogue of a random walk. While it is relatively well understood how quantum walks can speed up random walk hitting times, it is a long-standing open question to what extent quantum walks can speed up the spreading or mixing rate of random walks on graphs. In this expository paper, inspired by a blog post by Terence Tao, we describe a particular perspective on this question that derives quantum walks from the discrete wave equation on graphs. This yields a description of the quantum walk dynamics as simply applying a Chebyshev polynomial to the random walk transition matrix. This perspective decouples the problem from its quantum origin, and highlights connections to earlier (non-quantum) work and the use of Chebyshev polynomials in random walk theory as in the Varopoulos-Carne bound. We illustrate the approach by proving a weak limit of the quantum walk dynamics on the lattice. This gives a different proof of the quadratically improved spreading behavior of quantum walks on lattices.

arXiv:2402.07809•Feb 12, 2024•0 citations

Quantum and classical algorithms for graph classification and search problems

B. L. Douglas

[Truncated abstract] This thesis is split into three parts, each addressing the overarching theme of applying graph theoretic techniques to classi cation and search problems. Part I explores this theme in the context of quantum algorithms, in particular involving quantum walks, coined by Aharonov et al. in 1993 [1]. As a quantum analogue to classical random walks, quantum walks represent a promising candidate for quantum algorithms providing speed-ups over known classical methods. I will discuss two categories of quantum walk algorithms; quantum search and graph isomorphism. In particular, the e ciency of quantum walk based search algorithms on various families of graphs will be investigated, linking both e ciency of quantum circuit implementation and the complexity of the search problem to the symmetry of the underlying graphs. Several families of graphs are presented that are amenable to efficient quantum walk based searching, together with explicit quantum circuit implementations. In the case of the n-cube, I show that O(p2n) steps of a quanum walk are suffcient to nd a marked sub-d-cube (where d

•Jan 1, 2011•0 citations
The theme that underlies this thesis is the mutualist relation between classical walks and quantum walks on graphs, the latter being a promising algorithmic component of future quantum computers.We study both sides of this coin.On the one side we prove how classical walks can simulate quantum walks.This allows the use of folklore bounds on the behavior of classical walks to study speed limits on quantum walks, a question which had long evaded progress.On the other side, we prove how quantum walks can be used to speed up the behavior of a large class of classical walks.This leads to a new quantum algorithm which we call quantum walk fast-forwarding.We show that this algorithm allows to naturally speed up classical walk algorithms for search and property testing on graphs.The work is theoretical and mathematical, and supposed to be relevant for quantum computers that should some day exist.I feel proud of this work, and am indebted to many people.Foremost I must thank my supervisor Alain Sarlette, you have been the best supervisor I could wish for, if only for learning me that no-go proofs are traffic diversions rather than dead ends.
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 introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with PPP the Markov chain transition matrix and D=P∘PTD = \sqrt{P\circ P^T}D=P∘PT​ its discriminant matrix (D=PD=PD=P if PPP is symmetric), we construct a quantum walk algorithm that for any quantum state ∣v⟩|v\rangle∣v⟩ and integer ttt returns a quantum state εεε-close to the state Dt∣v⟩/∥Dt∣v⟩∥D^t|v\rangle/\|D^t|v\rangle\|Dt∣v⟩/∥Dt∣v⟩∥. The algorithm uses O(∥Dt∣v⟩∥−1tlog⁡(ε∥Dt∣v⟩∥)−1)O\Big(\|D^t|v\rangle\|^{-1}\sqrt{t\log(ε\|D^t|v\rangle\|)^{-1}}\Big)O(∥Dt∣v⟩∥−1tlog(ε∥Dt∣v⟩∥)−1​) expected quantum walk steps and O(∥Dt∣v⟩∥−1)O(\|D^t|v\rangle\|^{-1})O(∥Dt∣v⟩∥−1) expected reflections around ∣v⟩|v\rangle∣v⟩. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of sss-ttt connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = root P omicron P-T its discriminant matrix (D = P if P is symmetric), we construct a quantum walk algorithm that for any quantum state vertical bar v > and integer t returns a quantum state epsilon-close to the state D-t vertical bar v > /parallel to D-t vertical bar v > parallel to. The algorithm uses O(parallel to D-t vertical bar v > parallel to(-1) root t log(epsilon parallel to D-t vertical bar v > parallel to(-1)) expected quantum walk steps and O(parallel to D-t vertical bar v > parallel to(-1)) expected reflections around vertical bar v >. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
We introduce a new tool for quantum algorithms called quantum fast-forwarding (QFF). The tool uses quantum walks as a means to quadratically fast-forward a reversible Markov chain. More specifically, with P the Markov chain transition matrix and D = \sqrt{P\circ P^T} its discriminant matrix (D=P if P is symmetric), we construct a quantum walk algorithm that for any quantum state |v> and integer t returns a quantum state \epsilon-close to the state D^t|v>/\|D^t|v>. The algorithm uses O(|D^t|v>|^{-1}\sqrt{t\log(\epsilon\|D^t|v>})^{-1}}) expected quantum walk steps and O(\|D^t|v>|^{-1}) expected reflections around |v>. This shows that quantum walks can accelerate the transient dynamics of Markov chains, complementing the line of results that proves the acceleration of their limit behavior. We show that this tool leads to speedups on random walk algorithms in a very natural way. Specifically we consider random walk algorithms for testing the graph expansion and clusterability, and show that we can quadratically improve the dependency of the classical property testers on the random walk runtime. Moreover, our quantum algorithm exponentially improves the space complexity of the classical tester to logarithmic. As a subroutine of independent interest, we use QFF for determining whether a given pair of nodes lies in the same cluster or in separate clusters. This solves a robust version of s-t connectivity, relevant in a learning context for classifying objects among a set of examples. The different algorithms crucially rely on the quantum speedup of the transient behavior of random walks.
A quantum walk is the quantum analogue of a random walk. While it is relatively well understood how quantum walks can speed up random walk hitting times, it is a long-standing open question to what extent quantum walks can speed up the spreading or mixing rate of random walks on graphs. In this expository paper, inspired by a blog post by Terence Tao, we describe a particular perspective on this question that derives quantum walks from the discrete wave equation on graphs. This yields a description of the quantum walk dynamics as simply applying a Chebyshev polynomial to the random walk transition matrix. This perspective decouples the problem from its quantum origin, and highlights connections to earlier (non-quantum) work and the use of Chebyshev polynomials in random walk theory as in the Varopoulos-Carne bound. We illustrate the approach by proving a weak limit of the quantum walk dynamics on the lattice. This gives a different proof of the quadratically improved spreading behavior of quantum walks on lattices.
[Truncated abstract] This thesis is split into three parts, each addressing the overarching theme of applying graph theoretic techniques to classi cation and search problems. Part I explores this theme in the context of quantum algorithms, in particular involving quantum walks, coined by Aharonov et al. in 1993 [1]. As a quantum analogue to classical random walks, quantum walks represent a promising candidate for quantum algorithms providing speed-ups over known classical methods. I will discuss two categories of quantum walk algorithms; quantum search and graph isomorphism. In particular, the e ciency of quantum walk based search algorithms on various families of graphs will be investigated, linking both e ciency of quantum circuit implementation and the complexity of the search problem to the symmetry of the underlying graphs. Several families of graphs are presented that are amenable to efficient quantum walk based searching, together with explicit quantum circuit implementations. In the case of the n-cube, I show that O(p2n) steps of a quanum walk are suffcient to nd a marked sub-d-cube (where d