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

Shock-Capturing Quantum Algorithm for the Linear Advection Operator

Samuel Hagele, William Gregory, Yuan Shi

quant-phSubmitted Sep 17, 2026• Announced Sep 21, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textOverclaimsMissing comparisonStrong assumptionsPossible error

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

Related papers

A quantum algorithm for the lattice-Boltzmann method advection-diffusion equation

David M. Wawrzyniak, Josef M. Winter, Steffen J. Schmidt +4 more

We present a versatile and efficient quantum algorithm based on the Lattice Boltzmann method (LBM) approximate solution of the linear advection-diffusion equation (ADE). We emphasize that the LBM approximation modifies the diffusion term of the underlying exact ADE and leads to a modified equation (mADE). Due to its versatility in terms of operator splitting, the proposed quantum LBM algorithm for the mADE provides a building block for future quantum algorithms to solve the linearized Navier-Stokes equation on quantum computers. We split the algorithm into four operations: initialization, collision, streaming, and calculation of the macroscopic quantities. We propose general quantum building blocks for each operator, which adapt intrinsically from the general three-dimensional case to smaller dimensions and apply to arbitrary lattice-velocity sets. Based on (sub-linear) amplitude data encoding, we propose improved initialization and collision operations with reduced complexity and efficient sampling-based simulation. Quantum streaming algorithms are based on previous developments. The proposed quantum algorithm allows for the computation of successive time steps, requiring full state measurement and reinitialization after every time step. It is validated by comparison with a digital implementation and based on analytical solutions in one and two dimensions. Furthermore, we demonstrate the versatility of the quantum algorithm for two cases with non-uniform advection velocities in two and three dimensions. Various velocity sets are considered to further highlight the flexibility of the algorithm. We benchmark our optimized quantum algorithm against previous methods employed in sampling-based quantum simulators. We demonstrate sampling efficiency, with sampling accelerated convergence requiring fewer shots. • Novel LBM quantum algorithm for solving the linear advection-diffusion equation with variable velocity as a building block. • Modular quantum algorithm for 1 through 3 spatial dimensions and all common lattice-velocity sets. • Significant reduction in quantum-algorithm complexity achieved through efficient encoding strategy leveraging symmetries. • Improved collision quantum-algorithm building block leading to higher success rates for the collision operator. • Benchmarking shows faster convergence and reduced shot requirements compared to previous algorithms.

Computer Physics Communications•Sep 10, 2024•38 citations

Spectral quantum algorithm for passive scalar transport in shear flows

Philipp Pfeffer, Peter Brearley, Sylvain Laizet +1 more

The mixing of scalar substances in fluid flows by stirring and diffusion is ubiquitous in natural flows, chemical engineering, and microfluidic drug delivery. Here, we present a spectral quantum algorithm for scalar mixing by solving the advection-diffusion equation in a quantum computational fluid dynamics framework. The exact gate decompositions of the advection and diffusion operators in spectral space are derived. For all but the simplest one-dimensional flows, these operators do not commute. Therefore, we use operator splitting to construct quantum circuits capable of simulating arbitrary polynomial velocity profiles in multiple dimensions, such as the Blasius profile of a laminar boundary layer. Periodic, Neumann, and Dirichlet boundary conditions can be imposed with the appropriate quantum spectral transform. We evaluate the approach in statevector simulations of a Couette flow, plane Poiseuille flow, and a polynomial Blasius profile approximation. For an advection-diffusion problem in one dimension, we compare the time evolution of an ideal quantum simulation with those of real quantum computers with superconducting and trapped-ion qubits. The required number of two-qubit gates grows with the logarithm of the number of grid points raised to one higher power than the order of the polynomial velocity profile.

arXiv:2505.10136•Scientific Reports•Nov 21, 2025•6 citations

Unitary Quantum Algorithm for the Lattice-Boltzmann Method

David M. Wawrzyniak, Josef M. Winter, Steffen J. Schmidt +4 more

We present a quantum algorithm for computational fluid dynamics based on the Lattice-Boltzmann method. Our approach involves a novel encoding strategy and a modified collision operator, assuming full relaxation to the local equilibrium within a single time step. Our quantum algorithm enables the computation of multiple time steps in the linearized case, specifically for solving the advection-diffusion equation, before necessitating a full state measurement. Moreover, our formulation can be extended to compute the non-linear equilibrium distribution function for a single time step prior to measurement, utilizing the measurement as an essential algorithmic step. However, in the non-linear case, a classical postprocessing step is necessary for computing the moments of the distribution function. We validate our algorithm by solving the one dimensional advection-diffusion of a Gaussian hill. Our results demonstrate that our quantum algorithm captures non-linearity.

arXiv:2405.13391•May 22, 2024•8 citations

Two quantum algorithms for solving the one-dimensional advection–diffusion equation

Julia Ingelmann, Sachin S. Bharadwaj, Philipp Pfeffer +2 more

Two quantum algorithms are presented for the numerical solution of a linear one-dimensional advection–diffusion equation with periodic boundary conditions. Their accuracy and performance with increasing qubit number are compared point-by-point with each other. Specifically, we solve the linear partial differential equation with a Quantum Linear Systems Algorithm (QLSA) based on the Harrow–Hassidim–Lloyd method and a Variational Quantum Algorithm (VQA), for resolutions that can be encoded using up to 6 qubits, which corresponds to N=64 grid points on the unit interval. Both algorithms are hybrid in nature, i.e., they involve a combination of classical and quantum computing building blocks. The QLSA and VQA are solved as ideal statevector simulations using the in-house solver QFlowS and open-access Qiskit software, respectively. We discuss several aspects of both algorithms which are crucial for a successful performance in both cases. These are the accurate eigenvalue estimation with the quantum phase estimation for the QLSA and the choice of the algorithm of the minimization of the cost function for the VQA. The latter algorithm is also implemented in the noisy Qiskit framework including measurement noise. We reflect on the current limitations and suggest some possible routes of future research for the numerical simulation of classical fluid flows on a quantum computer.

arXiv:2401.00326•Computers & Fluids•Jul 18, 2024•45 citations

A probabilistic imaginary-time evolution quantum algorithm for advection-diffusion equation: Explicit gate-level implementation and comparisons to quantum linear system algorithms

Xinchi Huang, Hirofumi Nishi, Taichi Kosugi +2 more

Simulating differential equations on classical computers becomes an intractable problem if the grid size is extremely large. Quantum computers are believed to achieve a possibly exponential speedup in the matrix operation. In this paper, we propose a quantum algorithm for solving the advection-diffusion-reaction equation by employing a novel approximate probabilistic imaginary-time evolution (PITE) operator. First, the effectiveness of the proposed approximate PITE operator is justified by the theoretical evaluation of the error. Next, we construct the explicit quantum circuit to realize the imaginary-time evolution of the Hamiltonian coming from the advection-diffusion equation, whose gate complexity is logarithmic regarding the size of the discretized Hamiltonian matrix. Compared to the existing algorithms for the quantum linear system problem, our algorithm achieves an exponential speedup regarding the matrix size at the cost of a worse dependence on the error bound. Moreover, numerical simulations using gate-based quantum emulator for 1D/2D examples are also provided to verify our algorithm. Finally, we extend our algorithm to the coupled system of advection-diffusion equations to show the prospects for practical applications.

arXiv:2409.18559•Sep 27, 2024•11 citations

Schrödingerization for quantum linear systems problems

Yin Yang, Yue Yu, Long Zhang

We develop a Schrödingerization algorithm for quantum linear systems problems in two higher dimensions. The earlier LC-Schrödingerization approach represents the solution as a time integral of a homogeneous convection response and implements this integral by a linear combination of unitaries (LCU) over evolution times. We instead use Duhamel's principle to incorporate the integral into an inhomogeneous convection equation with zero initial data. Fourier projection in the convection variable and Schrödingerization in a second auxiliary variable then realize the solution without the separate LCU step. A joint choice of the kernel and recovery procedure gives an evolution time independent of the target accuracy, a uniformly bounded $L^2$ kernel normalization, and accurate recovery on a fixed interval. We establish the periodization and discretization bounds and analyze the interval recovery probability. With block preconditioning, we retain a single logarithmic precision factor and obtain linear condition-number dependence without variable-time amplitude amplification. Under exact oracle access and given a valid constant-factor solution-norm estimate, the algorithm uses $\mathcal O(κ_A\log(1/\varepsilon))$ queries to each original input oracle, with constant success probability and $\ell^2$ state error at most $\varepsilon$. The matrix-query bound matches the standard worst-case scaling when the supplied norm bounds are tight. UnitaryLab simulations on positive-definite and indefinite systems demonstrate the solution accuracy and probability gain from interval recovery.

quant-pharXiv:2609.25660•Sep 23, 2026•1 citation
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(n2)O(n^2)O(n2) two-qubit gates, where N=2nN=2^nN=2n is the number of spatial grid points, as opposed to a classical computer which costs O(N)O(N)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.
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=2nN=2^nN=2n points, and periodic boundaries, using the dissipative first-order upwind update T±=(1−f)I+fU±T^\pm=(1-f)I+fU^\pmT±=(1−f)I+fU±, where U±U^\pmU± shifts by one grid point and the CFL condition requires 0≤f≤10\leq f\leq10≤f≤1.
A single-ancilla linear-combination-of-unitaries circuit implements the update probabilistically. Explicit controlled-shift decompositions require O(n2)O(n^2)O(n2) 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→∞N\to\inftyN→∞. Reported failure bounds are O(N−1)O(N^{-1})O(N−1) for sufficiently smooth waveforms and O(N−1/2)O(N^{-1/2})O(N−1/2) for piecewise-smooth waveforms with jumps. Thus the expected amortized cost approaches O(log⁡2N)O(\log^2N)O(log2N) per step; propagation across the domain still requires O(N)O(N)O(N) steps.
A recovery procedure applies QFT, probabilistic multiplication by i/ki/ki/k, inverse QFT, and a half-step correction. Exact implementation costs O(nN)O(nN)O(nN); retaining a fixed number of low Fourier modes reduces recovery to O(n2)O(n^2)O(n2) 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)O(N)O(N), full-state readout removes the speedup, and efficient nonlinear components needed for broader fluid or plasma solvers remain undeveloped.
We present a versatile and efficient quantum algorithm based on the Lattice Boltzmann method (LBM) approximate solution of the linear advection-diffusion equation (ADE). We emphasize that the LBM approximation modifies the diffusion term of the underlying exact ADE and leads to a modified equation (mADE). Due to its versatility in terms of operator splitting, the proposed quantum LBM algorithm for the mADE provides a building block for future quantum algorithms to solve the linearized Navier-Stokes equation on quantum computers. We split the algorithm into four operations: initialization, collision, streaming, and calculation of the macroscopic quantities. We propose general quantum building blocks for each operator, which adapt intrinsically from the general three-dimensional case to smaller dimensions and apply to arbitrary lattice-velocity sets. Based on (sub-linear) amplitude data encoding, we propose improved initialization and collision operations with reduced complexity and efficient sampling-based simulation. Quantum streaming algorithms are based on previous developments. The proposed quantum algorithm allows for the computation of successive time steps, requiring full state measurement and reinitialization after every time step. It is validated by comparison with a digital implementation and based on analytical solutions in one and two dimensions. Furthermore, we demonstrate the versatility of the quantum algorithm for two cases with non-uniform advection velocities in two and three dimensions. Various velocity sets are considered to further highlight the flexibility of the algorithm. We benchmark our optimized quantum algorithm against previous methods employed in sampling-based quantum simulators. We demonstrate sampling efficiency, with sampling accelerated convergence requiring fewer shots. • Novel LBM quantum algorithm for solving the linear advection-diffusion equation with variable velocity as a building block. • Modular quantum algorithm for 1 through 3 spatial dimensions and all common lattice-velocity sets. • Significant reduction in quantum-algorithm complexity achieved through efficient encoding strategy leveraging symmetries. • Improved collision quantum-algorithm building block leading to higher success rates for the collision operator. • Benchmarking shows faster convergence and reduced shot requirements compared to previous algorithms.
The mixing of scalar substances in fluid flows by stirring and diffusion is ubiquitous in natural flows, chemical engineering, and microfluidic drug delivery. Here, we present a spectral quantum algorithm for scalar mixing by solving the advection-diffusion equation in a quantum computational fluid dynamics framework. The exact gate decompositions of the advection and diffusion operators in spectral space are derived. For all but the simplest one-dimensional flows, these operators do not commute. Therefore, we use operator splitting to construct quantum circuits capable of simulating arbitrary polynomial velocity profiles in multiple dimensions, such as the Blasius profile of a laminar boundary layer. Periodic, Neumann, and Dirichlet boundary conditions can be imposed with the appropriate quantum spectral transform. We evaluate the approach in statevector simulations of a Couette flow, plane Poiseuille flow, and a polynomial Blasius profile approximation. For an advection-diffusion problem in one dimension, we compare the time evolution of an ideal quantum simulation with those of real quantum computers with superconducting and trapped-ion qubits. The required number of two-qubit gates grows with the logarithm of the number of grid points raised to one higher power than the order of the polynomial velocity profile.
We present a quantum algorithm for computational fluid dynamics based on the Lattice-Boltzmann method. Our approach involves a novel encoding strategy and a modified collision operator, assuming full relaxation to the local equilibrium within a single time step. Our quantum algorithm enables the computation of multiple time steps in the linearized case, specifically for solving the advection-diffusion equation, before necessitating a full state measurement. Moreover, our formulation can be extended to compute the non-linear equilibrium distribution function for a single time step prior to measurement, utilizing the measurement as an essential algorithmic step. However, in the non-linear case, a classical postprocessing step is necessary for computing the moments of the distribution function. We validate our algorithm by solving the one dimensional advection-diffusion of a Gaussian hill. Our results demonstrate that our quantum algorithm captures non-linearity.
Two quantum algorithms are presented for the numerical solution of a linear one-dimensional advection–diffusion equation with periodic boundary conditions. Their accuracy and performance with increasing qubit number are compared point-by-point with each other. Specifically, we solve the linear partial differential equation with a Quantum Linear Systems Algorithm (QLSA) based on the Harrow–Hassidim–Lloyd method and a Variational Quantum Algorithm (VQA), for resolutions that can be encoded using up to 6 qubits, which corresponds to N=64 grid points on the unit interval. Both algorithms are hybrid in nature, i.e., they involve a combination of classical and quantum computing building blocks. The QLSA and VQA are solved as ideal statevector simulations using the in-house solver QFlowS and open-access Qiskit software, respectively. We discuss several aspects of both algorithms which are crucial for a successful performance in both cases. These are the accurate eigenvalue estimation with the quantum phase estimation for the QLSA and the choice of the algorithm of the minimization of the cost function for the VQA. The latter algorithm is also implemented in the noisy Qiskit framework including measurement noise. We reflect on the current limitations and suggest some possible routes of future research for the numerical simulation of classical fluid flows on a quantum computer.
Simulating differential equations on classical computers becomes an intractable problem if the grid size is extremely large. Quantum computers are believed to achieve a possibly exponential speedup in the matrix operation. In this paper, we propose a quantum algorithm for solving the advection-diffusion-reaction equation by employing a novel approximate probabilistic imaginary-time evolution (PITE) operator. First, the effectiveness of the proposed approximate PITE operator is justified by the theoretical evaluation of the error. Next, we construct the explicit quantum circuit to realize the imaginary-time evolution of the Hamiltonian coming from the advection-diffusion equation, whose gate complexity is logarithmic regarding the size of the discretized Hamiltonian matrix. Compared to the existing algorithms for the quantum linear system problem, our algorithm achieves an exponential speedup regarding the matrix size at the cost of a worse dependence on the error bound. Moreover, numerical simulations using gate-based quantum emulator for 1D/2D examples are also provided to verify our algorithm. Finally, we extend our algorithm to the coupled system of advection-diffusion equations to show the prospects for practical applications.
We develop a Schrödingerization algorithm for quantum linear systems problems in two higher dimensions. The earlier LC-Schrödingerization approach represents the solution as a time integral of a homogeneous convection response and implements this integral by a linear combination of unitaries (LCU) over evolution times. We instead use Duhamel's principle to incorporate the integral into an inhomogeneous convection equation with zero initial data. Fourier projection in the convection variable and Schrödingerization in a second auxiliary variable then realize the solution without the separate LCU step. A joint choice of the kernel and recovery procedure gives an evolution time independent of the target accuracy, a uniformly bounded L2L^2L2 kernel normalization, and accurate recovery on a fixed interval. We establish the periodization and discretization bounds and analyze the interval recovery probability. With block preconditioning, we retain a single logarithmic precision factor and obtain linear condition-number dependence without variable-time amplitude amplification. Under exact oracle access and given a valid constant-factor solution-norm estimate, the algorithm uses O(κAlog⁡(1/ε))\mathcal O(κ_A\log(1/\varepsilon))O(κA​log(1/ε)) queries to each original input oracle, with constant success probability and ℓ2\ell^2ℓ2 state error at most ε\varepsilonε. The matrix-query bound matches the standard worst-case scaling when the supplied norm bounds are tight. UnitaryLab simulations on positive-definite and indefinite systems demonstrate the solution accuracy and probability gain from interval recovery.