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

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 $\alpha$-perturbed $n$-cycle Markov chain, which preserves circulant structure while introducing controlled irreversibility. We show that the nonreversible case has a fundamental obstruction: for $\alpha \ne 0$, the eigenvalues of $P_{\alpha }$ leave the interval $[-1,1]$, so $T_m(P_{\alpha })$ 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_{\alpha }^t$ can be approximated with degree $\tau =O\left(|\alpha |t+\sqrt{t\log (t/\eta )}\right),$ which recovers the reversible $O(\sqrt{t})$ behavior only in the perturbative regime $|\alpha |=O(t^{-1/2})$. This identifies a nearly reversible regime where QFF survives perturbatively and quantifies how irreversibility degrades the speedup.

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