High-order quantum algorithm for solving linear differential equations

Abstract

Linear differential equations are ubiquitous in science and engineering. Quantum computers can simulate quantum systems, which are described by a restricted type of linear differential equations. Here we extend quantum simulation algorithms to general inhomogeneous sparse linear differential equations, which describe many classical physical systems. We examine the use of high-order methods to improve the efficiency. These provide scaling close to $\Delta t^2$ in the evolution time $\Delta t$. As with other algorithms of this type, the solution is encoded in amplitudes of the quantum state, and it is possible to extract global features of the solution.

14 pages, improved efficiency

References in corpus (6)

• Quantum algorithm for solving linear systems of equations
• Quantum Algorithms for Quantum Field Theories
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Preconditioned quantum linear system algorithm
• Experimental Quantum Computing to Solve Systems of Linear Equations

Cited by in corpus (104)

• A variational eigenvalue solver on a quantum processor
• Quantum algorithms: an overview
• A Theory of Trotter Error
• Variational quantum algorithms for nonlinear problems
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Variational Quantum State Diagonalization
• Solving nonlinear differential equations with differentiable quantum circuits
• Quantum algorithms and the finite element method
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum Algorithm for Simulating the Wave Equation
• Focus beyond quadratic speedups for error-corrected quantum advantage
• On the impact of quantum computing technology on future developments in high-performance scientific computing
• Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
• 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
• Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Time-marching based quantum solvers for time-dependent linear differential equations
• Quantum Fast Poisson Solver: the algorithm and modular circuit design
• Nearly tight Trotterization of interacting electrons
• On applications of quantum computing to plasma simulations
• Variational Quantum Solutions to the Advection-Diffusion Equation for Applications in Fluid Dynamics
• Exponential quantum speedup in simulating coupled classical oscillators
• 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 phase estimation for a class of generalized eigenvalue problems
• Quantum Computing for Fusion Energy Science Applications
• Box algorithm for the solution of differential equations on a quantum annealer
• FEqa: Finite Element Computations on Quantum Annealers
• Nonlinear dynamics as a ground-state solution on quantum computers
• Linear and logarithmic time compositions of quantum many-body operators
• 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
• Potential quantum advantage for simulation of fluid dynamics
• Quantum Circuits for partial differential equations via Schrödingerisation
• 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
• Synthesizing efficient circuits for Hamiltonian simulation
• 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 digital image processing
• A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations
• Fully quantum algorithm for lattice Boltzmann methods with application to partial differential equations
• Harrow-Hassidim-Lloyd algorithm without ancilla postselection
• A quantum algorithm for the linear Vlasov equation with collisions
• Boundary Treatment for Variational Quantum Simulations of Partial Differential Equations on Quantum Computers
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Opportunities and challenges of quantum computing for climate modelling
• 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
• Quantum Computing for Software Engineering: Prospects
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Quantum Quantitative Trading: High-Frequency Statistical Arbitrage Algorithm
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Tight Bound for Estimating Expectation Values from a System of Linear Equations
• Representation of the Fermionic Boundary Operator
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• Simulations of Future Particle Accelerators: Issues and Mitigations
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• Quantum algorithms for powering stable Hermitian matrices
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Quantum Newton's method for solving system of nonlinear algebraic equations
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Review of Quantum Algorithms for Systems of Linear Equations
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Improved resource-tunable near-term quantum algorithms for transition probabilities, with applications in physics and variational quantum linear algebra
• A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Quantum channel decomposition with pre- and post-selection
• Quantum Algorithm for Radiative Transfer Equation
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Hybrid classical-quantum image processing via polar Walsh basis functions
• Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics
• Multidimensional Quantum Generative Modeling by Quantum Hartley Transform
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm
• Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
• Quantum circuits for partial differential equations in Fourier space
• Preparing Many Copies of a Quantum State in the Black-Box Model
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• A quantum algorithm for linear autonomous differential equations via Padé approximation
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
• Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
• Quantum Realization of the Finite Element Method
• Quantum and classical algorithms for nonlinear unitary dynamics
• Error and Resource Estimates of Variational Quantum Algorithms for Solving Differential Equations Based on Runge-Kutta Methods
• Quantum Simulation-Based Optimization for Cooling System Design
• Quantum Algorithm For Solving Nonlinear Algebraic Equations
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm
• Solving the Nonlinear Vlasov Equation on a Quantum Computer