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:1804.02321 · Quantum Information and Computation

Quantum fast-forwarding: Markov chains and graph property testing

Simon Apers, Alain Scarlet

Published Mar 1, 2019• 65 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic19.3-4-1

Related papers

Faster quantum sampling of Markov chains in nonregular graphs with fewer qubits

Xinying Li, Yun Shang

Sampling from the stationary distribution is one of the fundamental tasks of Markov-chain-based algorithms and has important applications in machine learning, combinatorial optimization, and network science. For the quantum case, quantum sampling from Markov chains corresponds to preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution instead of classical sampling from a stationary distribution. A different quantum sampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks. We build a quantum sampling algorithm that not only accelerates nonregular graphs, but also keeps the speed up of existing quantum algorithms for regular graphs. In nonregular graphs, the invocation of the quantum fast-forwarding algorithm accelerates previous state-of-the-art quantum sampling algorithms for both discrete-time and continuous-time cases, especially on sparse graphs. Compared to existing algorithms, we decrease the runtime by a factor of $logn$, where $n$ is the number of graph vertices. In regular graphs, our results match other quantum algorithms and the reliance on the gap of Markov chains achieves quadratic speedup compared with classical cases. For both cases, we reduce the number of ancilla qubits required compared with the existing results. In some widely used graphs and a series of sparse graphs where stationary distributions are difficult to reach quickly, our algorithm achieves complete quadratic acceleration (without log factor) over the classical case without any limit. In addition, we construct a different reflection around the stationary state with fewer ancilla qubits and believe it may have an independent application.

arXiv:2205.06099•Physical Review A•Feb 27, 2023•4 citations

Quantum Fast-Forwarding Beyond Reversibility: The $α$-Perturbed $n$-Cycle

Avah Banerjee, Asim Sharma, Sooraj Soman

Quantum fast-forwarding (QFF) is usually formulated for reversible Markov chains, where the projected quantum walk evolution is exactly governed by Chebyshev polynomials of a Hermitian discriminant matrix. We study whether this framework can be extended to nonreversible dynamics for an $α$-perturbed $n$-cycle Markov chain, which preserves circulant structure while introducing controlled irreversibility. We show that the nonreversible case has a fundamental obstruction: for $α\neq 0$, the eigenvalues of $P_α$ leave the interval $[-1,1]$, so $T_m(P_α)$ is not uniformly bounded and cannot arise as an exact unitary compression for all times. Thus, exact Chebyshev-based QFF does not extend directly beyond reversibility. Nevertheless, we obtain a finite-time approximation result using truncated Chebyshev and LCU techniques. The evolution $P_α^t$ can be approximated with degree $τ=O\left(|α|t+\sqrt{t\log(t/η)}\right),$ which recovers the reversible $O(\sqrt t)$ behavior only in the perturbative regime $|α|=O(t^{-1/2})$. This identifies a nearly reversible regime where QFF survives perturbatively and quantifies how irreversibility degrades the speedup.

quant-pharXiv:2606.26584•Jun 26, 2026•2 citations

Expansion Testing using Quantum Fast-Forwarding and Seed Sets

Simon Apers

Expansion testing aims to decide whether an n -node graph has expansion at least Φ , or is far from any such graph. We propose a quantum expansion tester with complexity O~(n1/3Φ−1) . This accelerates the O~(n1/2Φ−2) classical tester by Goldreich and Ron [Algorithmica '02] \cite{goldreich2002property}, and combines the O~(n1/3Φ−2) and O~(n1/2Φ−1) quantum speedups by Ambainis, Childs and Liu [RANDOM '11] and Apers and Sarlette [QIC '19] \cite{apers2019quantum}, respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.

arXiv:1907.02369•Quantum•Sep 16, 2020•3 citations

Quantum Speed-Up of Markov Chain Based Algorithms

Márió Szegedy

We develop a generic method for quantizing classical algorithms based on random walks. We show that under certain conditions, the quantum version gives rise to a quadratic speed-up. This is the case, in particular, when the Markov chain is ergodic and its transition matrix is symmetric. This generalizes the celebrated result of L. K. Grover (1996)and a number of more recent results, including the element distinctness result of Ambainis and the result of Ambainis, Kempe and Rivosh that computes properties of quantum walks on the d-dimensional torus. Among the consequences is a faster search for multiple marked items. We show that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•629 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 walks : speed limits on mixing and fast-forwarding classical walks

Simon Apers

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.

•Jan 1, 2019•1 citation
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.
Sampling from the stationary distribution is one of the fundamental tasks of Markov-chain-based algorithms and has important applications in machine learning, combinatorial optimization, and network science. For the quantum case, quantum sampling from Markov chains corresponds to preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution instead of classical sampling from a stationary distribution. A different quantum sampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks. We build a quantum sampling algorithm that not only accelerates nonregular graphs, but also keeps the speed up of existing quantum algorithms for regular graphs. In nonregular graphs, the invocation of the quantum fast-forwarding algorithm accelerates previous state-of-the-art quantum sampling algorithms for both discrete-time and continuous-time cases, especially on sparse graphs. Compared to existing algorithms, we decrease the runtime by a factor of lognlognlogn, where nnn is the number of graph vertices. In regular graphs, our results match other quantum algorithms and the reliance on the gap of Markov chains achieves quadratic speedup compared with classical cases. For both cases, we reduce the number of ancilla qubits required compared with the existing results. In some widely used graphs and a series of sparse graphs where stationary distributions are difficult to reach quickly, our algorithm achieves complete quadratic acceleration (without log factor) over the classical case without any limit. In addition, we construct a different reflection around the stationary state with fewer ancilla qubits and believe it may have an independent application.
Quantum Fast-Forwarding Beyond Reversibility: The ααα-Perturbed nnn-Cycle
Quantum fast-forwarding (QFF) is usually formulated for reversible Markov chains, where the projected quantum walk evolution is exactly governed by Chebyshev polynomials of a Hermitian discriminant matrix. We study whether this framework can be extended to nonreversible dynamics for an ααα-perturbed nnn-cycle Markov chain, which preserves circulant structure while introducing controlled irreversibility. We show that the nonreversible case has a fundamental obstruction: for α≠0α\neq 0α=0, the eigenvalues of PαP_αPα​ leave the interval [−1,1][-1,1][−1,1], so Tm(Pα)T_m(P_α)Tm​(Pα​) is not uniformly bounded and cannot arise as an exact unitary compression for all times. Thus, exact Chebyshev-based QFF does not extend directly beyond reversibility. Nevertheless, we obtain a finite-time approximation result using truncated Chebyshev and LCU techniques. The evolution PαtP_α^tPαt​ can be approximated with degree τ=O(∣α∣t+tlog⁡(t/η)),τ=O\left(|α|t+\sqrt{t\log(t/η)}\right),τ=O(∣α∣t+tlog(t/η)​), which recovers the reversible O(t)O(\sqrt t)O(t​) behavior only in the perturbative regime ∣α∣=O(t−1/2)|α|=O(t^{-1/2})∣α∣=O(t−1/2). This identifies a nearly reversible regime where QFF survives perturbatively and quantifies how irreversibility degrades the speedup.
Expansion testing aims to decide whether an n -node graph has expansion at least Φ , or is far from any such graph. We propose a quantum expansion tester with complexity O~(n1/3Φ−1) . This accelerates the O~(n1/2Φ−2) classical tester by Goldreich and Ron [Algorithmica '02] \cite{goldreich2002property}, and combines the O~(n1/3Φ−2) and O~(n1/2Φ−1) quantum speedups by Ambainis, Childs and Liu [RANDOM '11] and Apers and Sarlette [QIC '19] \cite{apers2019quantum}, respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.
We develop a generic method for quantizing classical algorithms based on random walks. We show that under certain conditions, the quantum version gives rise to a quadratic speed-up. This is the case, in particular, when the Markov chain is ergodic and its transition matrix is symmetric. This generalizes the celebrated result of L. K. Grover (1996)and a number of more recent results, including the element distinctness result of Ambainis and the result of Ambainis, Kempe and Rivosh that computes properties of quantum walks on the d-dimensional torus. Among the consequences is a faster search for multiple marked items. We show that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted.
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.
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.