Quantum algorithm for linear differential equations with exponentially improved dependence on precision
arXiv:1701.03684 · doi:10.1007/s00220-017-3002-y
Abstract
We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.
arXiv comment20 pages, no figure; v2: minor revision
References in corpus (6)
- Quantum algorithm for solving linear systems of equations
- Quantum Amplitude Amplification and Estimation
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Efficient quantum algorithms for simulating sparse Hamiltonians
- High-order quantum algorithm for solving linear differential equations
Cited by in corpus (90)
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Solving nonlinear differential equations with differentiable quantum circuits
- Faster quantum simulation by randomization
- Quantum gradient descent for linear systems and least squares
- Quantum Algorithm for Simulating the Wave Equation
- Quantum Computing at the Frontiers of Biological Sciences
- Time-dependent Hamiltonian simulation with -norm scaling
- Quantum Machine Learning: from physics to software engineering
- Improved quantum algorithms for linear and nonlinear differential equations
- Quantum algorithm for non-homogeneous linear partial differential equations
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
- Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
- Time-marching based quantum solvers for time-dependent linear differential equations
- Quantum Fast Poisson Solver: the algorithm and modular circuit design
- Variational Quantum Solutions to the Advection-Diffusion Equation for Applications in Fluid Dynamics
- 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 algorithm for the Navier Stokes equations by using the streamfunction vorticity formulation and the lattice Boltzmann method
- Quantum Kernel Methods for Solving Differential Equations
- Variational quantum simulations of stochastic differential equations
- Quantum phase estimation for a class of generalized eigenvalue problems
- Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms
- Efficient quantum amplitude encoding of polynomial functions
- Application of a variational hybrid quantum-classical algorithm to heat conduction equation
- Quantum Computing for Fusion Energy Science Applications
- Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
- 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
- Quantum algorithm for time-dependent differential equations using Dyson series
- Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
- Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
- Quantum Circuits for partial differential equations via Schrödingerisation
- Potential quantum advantage for simulation of fluid dynamics
- Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations
- Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
- Variational Quantum Simulation of Partial Differential Equations: Applications in Colloidal Transport
- Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
- Quantum advantage for differential equation analysis
- Compact quantum algorithms for time-dependent differential equations
- A hybrid classical-quantum approach to solve the heat equation using quantum annealers
- Quantum algorithms for computing observables of nonlinear partial differential equations
- Quantum differential equation solvers: limitations and fast-forwarding
- A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations
- A quantum algorithm for the linear Vlasov equation with collisions
- Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
- Quantum algorithms for matrix operations and linear systems of equations
- Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
- Implementing smooth functions of a Hermitian matrix on a quantum computer
- Parallel Quantum Algorithm for Hamiltonian Simulation
- Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
- Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
- Quantum Quantitative Trading: High-Frequency Statistical Arbitrage Algorithm
- Probabilistic Eigensolver with a Trapped-Ion Quantum Processor
- Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
- Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
- Variational Quantum Algorithms for Differential Equations on a Noisy Quantum Computer
- A Quantum Search Decoder for Natural Language Processing
- Explicit block encodings of boundary value problems for many-body elliptic operators
- Quantum Newton's method for solving system of nonlinear algebraic equations
- Quantum algorithms for powering stable Hermitian matrices
- Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
- Quantum Algorithm for the Advection-Diffusion Equation by Direct Block Encoding of the Time-Marching Operator
- Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
- Quantum Computing for Data Centric Engineering and Science
- Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
- 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
- Computing scalar products via a two-terminal quantum transmission line
- Alternatives to a nonhomogeneous partial differential equation quantum algorithm
- Correspondence between open bosonic systems and stochastic differential equations
- Quantum channel decomposition with pre- and post-selection
- Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
- Quantum eigenvalue processing
- Quantum circuits for partial differential equations in Fourier space
- Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
- Existence and Uniqueness of Solutions of the Koopman--von Neumann Equation on Bounded Domains
- Quantum Realization of the Finite Element Method
- Quantum and classical algorithms for nonlinear unitary dynamics
- Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
- A quantum algorithm for linear autonomous differential equations via Padé approximation
- Quantum linear system algorithm with optimal queries to initial state preparation
- An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations
- Quantum Simulation-Based Optimization for Cooling System Design
- Error and Resource Estimates of Variational Quantum Algorithms for Solving Differential Equations Based on Runge-Kutta Methods
- Vortex Detection from Quantum Data
- Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
- Solving the Nonlinear Vlasov Equation on a Quantum Computer