arXiv:2609.21153
Shock-Capturing Quantum Algorithm for the Linear Advection Operator
Samuel Hagele, William Gregory, Yuan Shi
Abstract
The linear advection operator is an ubiquitous building block in fluid and plasma problems. We develop a quantum algorithm for enacting the operator. When the advection velocity is constant in space, our algorithm is exponentially more efficient per time step than classical and avoids spurious oscillations near steep gradients. The algorithm is most cleanly illustrated using the one-dimensional advection equation on a uniform spatial grid with periodic boundary conditions, which can be extended to higher dimensions. The algorithm uses a first-order upwind scheme, which captures discontinuities in the wave envelope but is not unitary. We embed the non-unitary upwind scheme using Linear Combinations of Unitaries (LCUs), and develop an efficient quantum gate decomposition of the upwind unitary, which performs one step of advection using $O(n^2)$ two-qubit gates, where $N=2^n$ is the number of spatial grid points, as opposed to a classical computer which costs $O(N)$. Although LCUs introduces a small bounded probability of failure per time step, we show that the accumulation of failures does not lead to exponential-in-time complexity as one would naively expect. Moreover, when LCUs fails, we develop a probabilistic scheme to recover from the failure state, which avoids a full restart of the simulation. The failure recovery scheme uses quantum Fourier transform (QFT) and effectively achieves quantum indefinite integration of an unknown quantum state. The recovery, which can itself fail, is more efficient than a full restart if the wave envelop is well-resolved to include only low Fourier modes. We emulate our scheme classically and demonstrate small problems on Quantinuum's trapped-ion qubits. Our quantum algorithm provides a subroutine for physics simulations that involve linear advection.
AI Summary
The paper addresses how to implement linear advection on a quantum computer without the oscillations near discontinuities associated with central-difference Hamiltonian methods. It considers constant velocity, a uniform one-dimensional grid with $N=2^n$ points, and periodic boundaries, using the dissipative first-order upwind update $T^\pm=(1-f)I+fU^\pm$, where $U^\pm$ shifts by one grid point and the CFL condition requires $0\leq f\leq1$. A single-ancilla linear-combination-of-unitaries circuit implements the update probabilistically. Explicit controlled-shift decompositions require $O(n^2)$ two-qubit gates per step. Fourier analysis shows that, for a fixed square-integrable initial waveform and fixed physical propagation distance, the probability of completing all steps without failure approaches one as $N\to\infty$. Reported failure bounds are $O(N^{-1})$ for sufficiently smooth waveforms and $O(N^{-1/2})$ for piecewise-smooth waveforms with jumps. Thus the expected amortized cost approaches $O(\log^2N)$ per step; propagation across the domain still requires $O(N)$ steps. A recovery procedure applies QFT, probabilistic multiplication by $i/k$, inverse QFT, and a half-step correction. Exact implementation costs $O(nN)$; retaining a fixed number of low Fourier modes reduces recovery to $O(n^2)$ overall. Recovery requires a zero-mean waveform and works best for low-frequency spectra. Circuit simulations demonstrate advection and recovery. Stated limitations include numerical diffusion, periodic boundaries, restricted recovery efficiency, and exponentially many time steps in qubit count. Generic state preparation costs $O(N)$, full-state readout removes the speedup, and efficient nonlinear components needed for broader fluid or plasma solvers remain undeveloped.
Error found: The abstract's exponential per-step efficiency claim requires qualifications: generic O(N) state preparation is amortized over Θ(N) steps, and the postselection guarantee concerns refinement of a fixed waveform rather than arbitrary grid-dependent inputs. The proposed untruncated failure recovery does not exactly restore the pre-failure state: its discrete Fourier multiplier is proportional to e^(−iθ)sin(θ)/θ, introducing translation and mode-dependent filtering. The supplied paper claims Quantinuum hardware demonstrations but reports only classical simulator results.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 24 pages, 8 figures, work presented at the 2025 APS Four Corners Meeting