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

arXiv:1804.02321•Quantum Information and Computation•Mar 1, 2019•65 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•7 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•1 citation

Stochastic Schrödinger Equations for Quantum Reverse Diffusion

Einar Gabbassov

The ensemble-averaged dynamics of open quantum systems are typically irreversible. We show that this irreversibility need not hold at the level of individually monitored quantum trajectories. Our main results are analytical stochastic Schrödinger equations for quantum reverse diffusion, along with corresponding stochastic master equations. These equations describe the exact and approximate stochastic reverse processes for continuously monitored Pauli channels, including time-dependent depolarizing noise. We show that the reverse processes generalize the forward dynamics by combining the noise effects of the forward processes with an additional stochastic drift that dynamically steers a quantum state back to its initial configuration. Consequently, the exact reverse stochastic Schrödinger equations admit closed-form solutions that can be implemented in real-time without the need for variational techniques. Our findings establish an analytical framework for quantum state recovery, noise-resilient quantum gates, quantum generative modelling, quantum tomography via forward-reverse cycles, and potential paradigms for quantum error correction based on reverse diffusion.

quant-pharXiv:2511.15919•Physical Review Research•Nov 21, 2025•4 citations

Quantum Fast Forwarding of Non-Markovian Quantum Dynamics

Avin Seneviratne, Peter Walters, Fei Wang

In this work, we present a quantum algorithm for simulating non-Markovian quantum dynamics based on the Feynman-Vernon influence functional formalism, which provides an exact description of the dynamics of a quantum system linearly coupled to a harmonic bath. In condensed-phase environments, the bath correlation functions typically decay over time, allowing them to be truncated beyond a finite time scale and enabling an iterative propagation scheme. We implement the finite-memory propagator using a fast-forwarding algorithm that achieves constant circuit depth with respect to the number of propagation steps, while the nonunitary matrices are realized on quantum circuits using unitary dilation. We further exploit the structure of the unitary dilation to show that the additional circuit complexity introduced by the dilation scales polynomially with the number of dilation ancilla qubits, while the dominant computational cost arises from the implementation of the underlying 1-dilation. The algorithm is compared with classical benchmark calculations for the spin-boson model and shows close agreement. Together, these developments establish a quantum-circuit framework for fast forwarding non-Markovian dynamics and identify the principal computational bottlenecks that must be overcome to achieve quantum advantage.

The Journal of Physical Chemistry Letters•Oct 12, 2026•0 citations

Quantum vs classical Markov chains; Exactly solvable examples

Ryu Sasaki B

A coinless quantisation procedure of general reversible Markov chains on graphs is presented. A quantum Hamiltonian H is obtained by a similarity transformation of the fundamental transition probability matrix K in terms of the square root of the reversible distribution. The evolution of the classical and quantum Markov chains is described by the solutions of the eigenvalue problem of the quantum Hamiltonian H. About twenty plus exactly solvable Markov chains based on the hypergeometric orthogonal polynomials of Askey scheme, derived by Odake-Sasaki, would provide a good window for scrutinising the quantum/classical contrast of Markov chains. Among them five explicit examples, related to the Krawtchouk, Hahn, q-Hahn, Charlier and Meixner, are demonstrated to illustrate the actual calculations.

arXiv:2212.10713•Dec 21, 2022•3 citations
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 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 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.
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.
The ensemble-averaged dynamics of open quantum systems are typically irreversible. We show that this irreversibility need not hold at the level of individually monitored quantum trajectories. Our main results are analytical stochastic Schrödinger equations for quantum reverse diffusion, along with corresponding stochastic master equations. These equations describe the exact and approximate stochastic reverse processes for continuously monitored Pauli channels, including time-dependent depolarizing noise. We show that the reverse processes generalize the forward dynamics by combining the noise effects of the forward processes with an additional stochastic drift that dynamically steers a quantum state back to its initial configuration. Consequently, the exact reverse stochastic Schrödinger equations admit closed-form solutions that can be implemented in real-time without the need for variational techniques. Our findings establish an analytical framework for quantum state recovery, noise-resilient quantum gates, quantum generative modelling, quantum tomography via forward-reverse cycles, and potential paradigms for quantum error correction based on reverse diffusion.
In this work, we present a quantum algorithm for simulating non-Markovian quantum dynamics based on the Feynman-Vernon influence functional formalism, which provides an exact description of the dynamics of a quantum system linearly coupled to a harmonic bath. In condensed-phase environments, the bath correlation functions typically decay over time, allowing them to be truncated beyond a finite time scale and enabling an iterative propagation scheme. We implement the finite-memory propagator using a fast-forwarding algorithm that achieves constant circuit depth with respect to the number of propagation steps, while the nonunitary matrices are realized on quantum circuits using unitary dilation. We further exploit the structure of the unitary dilation to show that the additional circuit complexity introduced by the dilation scales polynomially with the number of dilation ancilla qubits, while the dominant computational cost arises from the implementation of the underlying 1-dilation. The algorithm is compared with classical benchmark calculations for the spin-boson model and shows close agreement. Together, these developments establish a quantum-circuit framework for fast forwarding non-Markovian dynamics and identify the principal computational bottlenecks that must be overcome to achieve quantum advantage.
A coinless quantisation procedure of general reversible Markov chains on graphs is presented. A quantum Hamiltonian H is obtained by a similarity transformation of the fundamental transition probability matrix K in terms of the square root of the reversible distribution. The evolution of the classical and quantum Markov chains is described by the solutions of the eigenvalue problem of the quantum Hamiltonian H. About twenty plus exactly solvable Markov chains based on the hypergeometric orthogonal polynomials of Askey scheme, derived by Odake-Sasaki, would provide a good window for scrutinising the quantum/classical contrast of Markov chains. Among them five explicit examples, related to the Krawtchouk, Hahn, q-Hahn, Charlier and Meixner, are demonstrated to illustrate the actual calculations.