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:2606.26584

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

Avah Banerjee, Asim Sharma, Sooraj Soman

quant-phSubmitted Jun 25, 2026• Announced Jun 26, 2026• 0 citations• Revised Jun 26, 2026 (v2)
v1 · Jun 25, 2026v2 · Jun 26, 2026
arXivHTMLPDF

Abstract

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.

Comments
25 pages, correction of a typo in one of the authors' names

Related papers

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

ApersSimon, SarletteAlain

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

Quantum Information and Computation•Mar 1, 2019•4 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 Markov State Models for Metastable Dynamics

Hao-En Li, Lin Lin, Michael Ragone

Open quantum systems can rapidly lose most microscopic information, leaving only a few degrees of freedom to govern their long-time dynamics. Classical Markov state models (MSMs) describe such metastable dynamics as transitions among a few representative phases and are widely used to reduce complex-system dynamics in condensed matter and chemical physics. In quantum systems, however, phase labels alone are insufficient when coherence persists between metastable states. Even when the slow modes are known, their spectral projection need not produce valid quantum states. We construct quantum Markov state models (QMSMs) that describe the surviving information and its evolution on a small physical state space containing classical sectors and quantum matrix blocks. We quantify metastability by assuming that the evolution channel $\mathcal C$ changes little when applied a second time, with sufficiently small defect $η=\|\mathcal C^2-\mathcal C\|_\diamond$, and that the number of slow degrees of freedom is bounded independently of the full system size. Under these assumptions, we construct compression and reconstruction channels whose composition recovers every reduced state exactly, while the reverse composition gives an exactly idempotent channel approximating $\mathcal C$, answering Kitaev's exact-rounding question [Kit25]. Our constructions give an optimal diamond-norm bound of $\mathcal{O}(η^{1/3})$ on all input states, as well as an improved bound of $\mathcal{O}(η^{1/2})$ on metastable states prepared by $\mathcal C$, with constants depending only on the slow dimension. The reduced transition channel can be iterated to predict the microscopic dynamics with controlled error. We illustrate the QMSM through a weakly driven dissipative spin chain supporting either a metastable logical qubit or long-lived classical phases.

quant-pharXiv:2609.40214•Oct 1, 2026•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 = 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 speedup for nonreversible Markov chains

Baptiste Claudon, Jean‐Philip Piquemal, Pierre Monmarché

Quantum algorithms can potentially solve a handful of problems more efficiently than their classical counterparts. In that context, it has been discussed that Markov chains problems could be solved significantly faster using quantum computing. Indeed, previous work suggests that quantum computers could accelerate sampling from the stationary distribution of reversible Markov chains. However, in practice, certain physical processes of interest are nonreversible in the probabilistic sense and reversible Markov chains can sometimes be replaced by more efficient nonreversible chains targeting the same stationary distribution. This study constructs Markov chain reversibilizations and develops quantum algorithmic techniques to accelerate nonreversible processes. Such an up-to-exponential quantum speedup goes beyond the predicted quadratic quantum acceleration for reversible chains and is likely to have a decisive impact on many applications ranging from statistics and machine learning to computational modeling in physics, chemistry, biology and finance.

arXiv:2501.05868•Nature Communications•Nov 28, 2025•1 citation
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.
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 = \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.
Open quantum systems can rapidly lose most microscopic information, leaving only a few degrees of freedom to govern their long-time dynamics. Classical Markov state models (MSMs) describe such metastable dynamics as transitions among a few representative phases and are widely used to reduce complex-system dynamics in condensed matter and chemical physics. In quantum systems, however, phase labels alone are insufficient when coherence persists between metastable states. Even when the slow modes are known, their spectral projection need not produce valid quantum states. We construct quantum Markov state models (QMSMs) that describe the surviving information and its evolution on a small physical state space containing classical sectors and quantum matrix blocks. We quantify metastability by assuming that the evolution channel C\mathcal CC changes little when applied a second time, with sufficiently small defect η=∥C2−C∥⋄η=\|\mathcal C^2-\mathcal C\|_\diamondη=∥C2−C∥⋄​, and that the number of slow degrees of freedom is bounded independently of the full system size. Under these assumptions, we construct compression and reconstruction channels whose composition recovers every reduced state exactly, while the reverse composition gives an exactly idempotent channel approximating C\mathcal CC, answering Kitaev's exact-rounding question [Kit25]. Our constructions give an optimal diamond-norm bound of O(η1/3)\mathcal{O}(η^{1/3})O(η1/3) on all input states, as well as an improved bound of O(η1/2)\mathcal{O}(η^{1/2})O(η1/2) on metastable states prepared by C\mathcal CC, with constants depending only on the slow dimension. The reduced transition channel can be iterated to predict the microscopic dynamics with controlled error. We illustrate the QMSM through a weakly driven dissipative spin chain supporting either a metastable logical qubit or long-lived classical phases.
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.
Quantum algorithms can potentially solve a handful of problems more efficiently than their classical counterparts. In that context, it has been discussed that Markov chains problems could be solved significantly faster using quantum computing. Indeed, previous work suggests that quantum computers could accelerate sampling from the stationary distribution of reversible Markov chains. However, in practice, certain physical processes of interest are nonreversible in the probabilistic sense and reversible Markov chains can sometimes be replaced by more efficient nonreversible chains targeting the same stationary distribution. This study constructs Markov chain reversibilizations and develops quantum algorithmic techniques to accelerate nonreversible processes. Such an up-to-exponential quantum speedup goes beyond the predicted quadratic quantum acceleration for reversible chains and is likely to have a decisive impact on many applications ranging from statistics and machine learning to computational modeling in physics, chemistry, biology and finance.