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.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.02321Apr 6, 201812 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.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, 20190 citations

Quantum fast-forwarding

ApersSimon, SarletteAlain

Quantum Information and ComputationMar 1, 20194 citations

Quantum Fast-Forwarding Beyond Reversibility: The $α$ -Perturbed $n$ -CycleQuantum 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.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.26584Jun 26, 20260 citations

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.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.06099Physical Review AFeb 27, 20232 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.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.02369QuantumSep 16, 20202 citations

P

the Markov chain transition matrix and

D = \sqrt{P\circ P^T}

its discriminant matrix (

D=P

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.

Quantum Fast-Forwarding Beyond Reversibility: The

α

-Perturbed

n

-Cycle

α

-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.

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.