Efficient quantum algorithm for dissipative nonlinear differential equations

Abstract

Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic $n$-dimensional ordinary differential equations. Assuming $R<1$, where $R$ is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity $T^{2}q\mathrm{poly}(\log T,\log n,\log 1/\epsilon )/\epsilon$, where $T$ is the evolution time, $\epsilon$ is the allowed error, and $q$ measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in $T$. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a novel convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for $R\ge \sqrt{2}$. Finally, we discuss potential applications, showing that the $R<1$ condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of $R$.

36 pages, 1 figure. Updated to reflect a correction to the version published in PNAS (https://doi.org/10.1073/pnas.2615307123)

References in corpus (19)

• Quantum algorithm for solving linear systems of equations
• Synthesis of Quantum Logic Circuits
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Preconditioned quantum linear system algorithm
• High-order quantum algorithm for solving linear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum algorithms and the finite element method
• Quantum algorithm and circuit design solving the Poisson equation
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• NP-complete Problems and Physical Reality
• Quantum spectral methods for differential equations
• Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
• Quantum Algorithm for the Vlasov Equation
• A quantum algorithm to solve nonlinear differential equations
• Optimal state discrimination and unstructured search in nonlinear quantum mechanics
• Quantum algorithm for nonlinear differential equations
• Explicit Error Bounds for Carleman Linearization
• Quantum vs. classical algorithms for solving the heat equation

Cited by in corpus (121)

• Computational advantage of quantum random sampling
• A Quantum Inspired Approach to Exploit Turbulence Structures
• Improved quantum algorithms for linear and nonlinear differential equations
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Towards provably efficient quantum algorithms for large-scale machine-learning models
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
• Time-marching based quantum solvers for time-dependent linear differential equations
• Variational Quantum Solutions to the Advection-Diffusion Equation for Applications in Fluid Dynamics
• On applications of quantum computing to plasma simulations
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Quantum Kernel Methods for Solving Differential Equations
• Quantum simulation of partial differential equations via Schrodingerisation
• Hybrid quantum algorithms for flow problems
• Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
• Quantum algorithms for approximate function loading
• Lattice Boltzmann-Carleman quantum algorithm and circuit for fluid flows at moderate Reynolds number
• Efficient quantum amplitude encoding of polynomial functions
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods
• Quantum Computing for Fusion Energy Science Applications
• Three Carleman routes to the quantum simulation of classical fluids
• Towards quantum computing for clinical trial design and optimization: A perspective on new opportunities and challenges
• Variational Quantum Evolution Equation Solver
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Two quantum algorithms for solving the one-dimensional advection-diffusion equation
• An Alternative Approach to Quantum Imaginary Time Evolution
• Nonlinear dynamics as a ground-state solution on quantum computers
• FEqa: Finite Element Computations on Quantum Annealers
• Noisy intermediate-scale quantum simulation of the one-dimensional wave equation
• Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
• Analog quantum simulation of partial differential equations
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Simulating unsteady fluid flows on a superconducting quantum processor
• Potential quantum advantage for simulation of fluid dynamics
• Variational Quantum-Based Simulation of Waveguide Modes
• Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations
• Towards Cosmological Simulations of Dark Matter on Quantum Computers
• Reduced-order modeling of two-dimensional turbulent Rayleigh-Bénard flow by hybrid quantum-classical reservoir computing
• Quantum computing of reacting flows via Hamiltonian simulation
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
• Enabling Large-Scale and High-Precision Fluid Simulations on Near-Term Quantum Computers
• Simulating fluid flows with quantum computing
• Efficient and fail-safe quantum algorithm for the transport equation
• Quantum advantage for differential equation analysis
• Compact quantum algorithms for time-dependent differential equations
• Quantum algorithms for scientific computing
• Quantum algorithms for computing observables of nonlinear partial differential equations
• Quantum-Inspired Fluid Simulation of 2D Turbulence with GPU Acceleration
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Quantum differential equation solvers: limitations and fast-forwarding
• Noise-Resistant Quantum State Compression Readout
• Fully quantum algorithm for lattice Boltzmann methods with application to partial differential equations
• A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations
• A quantum algorithm for the linear Vlasov equation with collisions
• Observation of a non-Hermitian supersonic mode on a trapped-ion quantum computer
• Koopman wavefunctions and Clebsch variables in Vlasov-Maxwell kinetic theory
• Efficient Quantum Lattice Gas Automata
• Explicit Quantum Circuit for Simulating the Advection-Diffusion-Reaction Dynamics
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Quantum Computing for Software Engineering: Prospects
• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Numerical solution of nonlinear Schrödinger equation by a hybrid pseudospectral-variational quantum algorithm
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Tight Bound for Estimating Expectation Values from a System of Linear Equations
• Black-Box Quantum State Preparation with Inverse Coefficients
• Solving Fractional Differential Equations on a Quantum Computer: A Variational Approach
• A Comprehensive Cross-Model Framework for Benchmarking the Performance of Quantum Hamiltonian Simulations
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Quantum algorithms for matrix geometric means
• An invitation to the sample complexity of quantum hypothesis testing
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Observability of fidelity decay at the Lyapunov rate in few-qubit quantum simulations
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• Quantum computing for simulation of fluid dynamics
• Quantum homotopy analysis method with quantum-compatible linearization for nonlinear partial differential equations
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Simulating nonlinear optical processes on a superconducting quantum device
• Quantum Dynamics Simulation of the Advection-Diffusion Equation
• Data Assimilation in Operator Algebras
• Quantum Computing for Data Centric Engineering and Science
• A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm
• Impact of dynamics, entanglement, and Markovian noise on the fidelity of few-qubit digital quantum simulation
• Quantum Simulation of Nonlinear Dynamical Systems Using Repeated Measurement
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Correspondence between open bosonic systems and stochastic differential equations
• Quantum circuits for partial differential equations in Fourier space
• Quantum channel decomposition with pre- and post-selection
• Quantum and classical algorithms for nonlinear unitary dynamics
• Existence and Uniqueness of Solutions of the Koopman--von Neumann Equation on Bounded Domains
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Reachability of weakly nonlinear systems using Carleman linearization
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• Estimating QSVT angles for matrix inversion with large condition numbers
• Quantum Calculation for Two-Stream Instability and Advection Test of Vlasov-Maxwell Equations: Numerical Evaluation of Hamiltonian Simulation
• A time-marching quantum algorithm for simulation of the nonlinear Lorenz dynamics
• Quantum implicit representation of vortex filaments in turbulence
• An Efficient Decomposition of the Carleman Linearized Burgers' Equation
• Divergence-free algorithms for solving nonlinear differential equations on quantum computers
• Solving Differential Equations via Continuous-Variable Quantum Computers
• A Fractional Calculus Framework for Open Quantum Dynamics: From Liouville to Lindblad to Memory Kernels
• The universe as a nonlinear quantum simulation: Large $n$ limit of the central spin model
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm
• Quantum Encoding of Structured Data with Matrix Product States
• Quantum Algorithm For Solving Nonlinear Algebraic Equations
• Nonlinear path-following via the asymptotic numerical method on a quantum processor
• Vortex Detection from Quantum Data
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
• Fully Quantum Algorithm for the 1-dimensional linear Lattice Boltzmann Method
• Koopman and transfer operator techniques from the perspective of quantum theory
• Solving the Nonlinear Vlasov Equation on a Quantum Computer
• Some Comments on Unitary Qubit Lattice Algorithms for Classical Problems
• Quantum Simulation-Based Optimization for Cooling System Design
• Analysis of Carlemann Linearization of Lattice Boltzmann