Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
arXiv:2410.03985 · doi:10.1016/j.cpc.2025.109498
Abstract
We propose an explicit algorithm based on the Linear Combination of Hamiltonian Simulations technique to simulate both the advection-diffusion equation and a nonunitary discretized version of the Koopman-von Neumann formulation of nonlinear dynamics. By including dissipation into the model, through an upwind discretization of the advection operator, we avoid spurious parasitic oscillations which usually accompany standard finite difference discretizations of the advection equation. In contrast to prior works on quantum simulation of nonlinear problems, we explain in detail how different components of the algorithm can be implemented by using the Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) methods. In addition, we discuss the general method for implementing the block-encoding (BE) required for QSP and QSVT circuits and provide explicit implementations of the BE oracles tailored to our specific test cases. We simulate the resulting circuit on a digital emulator of quantum fault-tolerant computers and investigate its complexity and success probability. The proposed algorithm is universal and can be used for modeling a broad class of linear and nonlinear differential equations including the KvN and Carleman embeddings of nonlinear systems, the semiclassical Koopman-van Hove (KvH) equation, as well as the advection and Liouville equations.
References in corpus (34)
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- A short introduction to the Lindblad Master Equation
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum speedup of Monte Carlo methods
- QuEST and High Performance Simulation of Quantum Computers
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Solving nonlinear differential equations with differentiable quantum circuits
- Efficient phase-factor evaluation in quantum signal processing
- Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
- Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
- Variational Quantum Algorithms for Computational Fluid Dynamics
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- Product Decomposition of Periodic Functions in Quantum Signal Processing
- Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
- Time-marching based quantum solvers for time-dependent linear differential equations
- Variational Quantum Solutions to the Advection-Diffusion Equation for Applications in Fluid Dynamics
- Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
- Exponential quantum speedup in simulating coupled classical oscillators
- Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
- Practical Quantum Computing: solving the wave equation using a quantum approach
- Block-encoding structured matrices for data input in quantum computing
- Quantum Resources Required to Block-Encode a Matrix of Classical Data
- Quantum Computing for Fusion Energy Science Applications
- Quantum computing of reacting flows via Hamiltonian simulation
- Polylogarithmic-depth controlled-NOT gates without ancilla qubits
- Quantum Signal Processing for simulating cold plasma waves
- Koopman wavefunctions and Clebsch variables in Vlasov-Maxwell kinetic theory
- A quantum annealing-sequential quadratic programming assisted finite element simulation for non-linear and history-dependent mechanical problems
- Simulation of linear non-Hermitian boundary-value problems with quantum singular value transformation
- Semiclassical Theory and the Koopman-van Hove Equation
- Encoding of linear kinetic plasma problems in quantum circuits via data compression
- Correspondence between open bosonic systems and stochastic differential equations
Cited by in corpus (6)
- Quantum Algorithm for the Advection-Diffusion Equation by Direct Block Encoding of the Time-Marching Operator
- Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
- A time-marching quantum algorithm for simulation of the nonlinear Lorenz dynamics
- Koopman and transfer operator techniques from the perspective of quantum theory
- Simulating plasma wave propagation on a superconducting quantum chip
- An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations