High-precision quantum algorithms for partial differential equations
arXiv:2002.07868 · doi:10.22331/q-2021-11-10-574
Abstract
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity , where is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be , where is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
40 pages. Corrected the dependence on the dimension of the finite difference method
References in corpus (6)
- Quantum algorithm for solving linear systems of equations
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Synthesis of Quantum Logic Circuits
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- Quantum algorithm and circuit design solving the Poisson equation
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
Cited by in corpus (73)
- Efficient quantum algorithm for dissipative nonlinear differential equations
- The prospects of quantum computing in computational molecular biology
- Solving nonlinear differential equations with differentiable quantum circuits
- Variational Quantum algorithm for Poisson equation
- Improved quantum algorithms for linear and nonlinear differential equations
- Biology and medicine in the landscape of quantum advantages
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
- 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 simulation of partial differential equations via Schrodingerisation
- Hybrid quantum algorithms for flow problems
- Quantum Variational Solving of Nonlinear and Multi-Dimensional Partial Differential Equations
- Quantum Computing for Fusion Energy Science Applications
- 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
- 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 simulation of real-space dynamics
- Analog quantum simulation of partial differential equations
- Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
- Towards Quantum Computational Mechanics
- Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
- Quantum algorithm for time-dependent differential equations using Dyson series
- 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
- Quantum computing of reacting flows via Hamiltonian simulation
- Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
- Efficient Hamiltonian Simulation for Solving Option Price Dynamics
- Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
- Polylogarithmic-depth controlled-NOT gates without ancilla qubits
- Simulating fluid flows with quantum computing
- On efficient quantum block encoding of pseudo-differential operators
- Quantum algorithms for scientific computing
- Compact quantum algorithms for time-dependent differential equations
- Quantum algorithms for computing observables of nonlinear partial differential equations
- Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
- Fully quantum algorithm for lattice Boltzmann methods with application to partial differential equations
- Harrow-Hassidim-Lloyd algorithm without ancilla postselection
- On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
- Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
- Quantum state preparation for multivariate functions
- Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
- Quantum algorithms for escaping from saddle points
- Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
- Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
- Protocols for Trainable and Differentiable Quantum Generative Modelling
- Quantum Finite Volume Method for Computational Fluid Dynamics with Classical Input and Output
- Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
- Quantum algorithms for matrix geometric means
- Explicit block encodings of boundary value problems for many-body elliptic operators
- Simulations of Future Particle Accelerators: Issues and Mitigations
- Quantum Algorithm for Smoothed Particle Hydrodynamics
- An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
- Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
- Pricing multi-asset derivatives by finite difference method on a quantum computer
- Quantum Computing for Data Centric Engineering and Science
- Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States
- Correspondence between open bosonic systems and stochastic differential equations
- Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
- Quantum Algorithm for Radiative Transfer Equation
- Alternatives to a nonhomogeneous partial differential equation quantum algorithm
- Quantum circuits for partial differential equations in Fourier space
- Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
- Quantum Realization of the Finite Element Method
- Fully Quantum Algorithm for the 1-dimensional linear Lattice Boltzmann Method
- Spectral quantum algorithm for passive scalar transport in shear flows
- Solving the Nonlinear Vlasov Equation on a Quantum Computer
- Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs