Quantum spectral methods for differential equations

Abstract

Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a $d$-dimensional system of linear equations or linear differential equations with complexity $\mathrm{poly}(\log d)$. While several of these algorithms approximate the solution to within $\epsilon$ with complexity $\mathrm{poly}(\log (1/\epsilon ))$, no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity $\mathrm{poly}(\log d,\log (1/\epsilon ))$.

29 pages

Cited by in corpus (61)

• 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
• High-precision quantum algorithms for partial differential equations
• Quantum Computing at the Frontiers of Biological Sciences
• 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
• 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
• 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 Computing for Fusion Energy Science Applications
• Quantum Algorithm for Solving the Advection Equation using Hamiltonian Simulation
• Quantum algorithm for time-dependent differential equations using Dyson series
• An efficient quantum algorithm for preparation of uniform quantum superposition states
• 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
• Enabling Large-Scale and High-Precision Fluid Simulations on Near-Term Quantum Computers
• A hybrid quantum-classical framework for computational fluid dynamics
• Quantum support vector machines for aerodynamic classification
• On quantum algorithms for the Schrödinger equation in the semi-classical regime
• Quantum differential equation solvers: limitations and fast-forwarding
• 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
• Boundary Treatment for Variational Quantum Simulations of Partial Differential Equations on Quantum Computers
• A quantum algorithm for the linear Vlasov equation with collisions
• Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems
• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
• 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 Carleman linearisation efficiency in nonlinear fluid dynamics
• Protocols for Trainable and Differentiable Quantum Generative Modelling
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• A generalization of Bernstein-Vazirani algorithm with multiple secret keys and a probabilistic oracle
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Quantum Newton's method for solving system of nonlinear algebraic equations
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Quantum homotopy analysis method with quantum-compatible linearization for nonlinear partial differential equations
• 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
• 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
• 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
• A Quantum-Inspired Algorithm for Wave Simulation Using Tensor Networks
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
• A quantum algorithm for linear autonomous differential equations via Padé approximation
• Existence and Uniqueness of Solutions of the Koopman--von Neumann Equation on Bounded Domains
• Quantum Realization of the Finite Element Method
• A quantum approach for optimal control
• Quantum neural network autoencoder and classifier applied to an industrial case study
• Efficient quantum algorithm for weighted partial sums and numerical integration
• Solving the Nonlinear Vlasov Equation on a Quantum Computer