Quantum spectral methods for differential equations

DOI10.1007/S00220-020-03699-ZMaRDI QIDQ2174656zbMATH OpenOpenAlexFDO

Authors Andrew M. Childs, Jin-Peng Liu

Publication date 21 April 2020

Published in Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.00961

zbMATH Keywords

complexityboundary value problemCauchy problemcondition numberquantum algorithmlinear ordinary differential equationChebyshev collocationsuccess probabilitysolution errorstate preparation procedure

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Numerical solution of boundary value problems involving ordinary differential equations (65L10) Finite element, Rayleigh-Ritz, Galerkin and collocation methods for ordinary differential equations (65L60) Numerical methods for initial value problems involving ordinary differential equations (65L05)

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 $mathrmpoly(logd)$. While several of these algorithms approximate the solution to within $epsilon$ with complexity $mathrmpoly(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 $mathrmpoly(logd,log(1/epsilon))$.

Recommendations

• Spectral methods in computational quantum mechanics
• scientific article; zbMATH DE number 5983594
• scientific article; zbMATH DE number 2113703
• Numerical Methods for Solving Spectral Problems on Quantum Graphs
• Spectral methods in quantum field theory
• Semi-spectral Chebyshev method in quantum mechanics
• Investigation of spectral analysis of matrix quantum difference equations with spectral singularities
• A spectral approach to quantum stochastic integrals
• Spectral differentiation matrices for the numerical solution of Schrödinger's equation
• Various approaches to spectral problems for integrable systems in the QISM.

Cites work

• scientific article; zbMATH DE number 48872 (Why is no real title available?)
• scientific article; zbMATH DE number 1167864 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A modified pseudospectral method for numerical solution of ordinary differential equations systems
• A modified spectral method for numerical solution of ordinary differential equations with non-analytic solution
• Efficient quantum algorithms for simulating sparse Hamiltonians
• High-order quantum algorithm for solving linear differential equations
• On the relationship between continuous- and discrete-time quantum walk
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Spectral methods for differential problems
• Spectral methods. Algorithms, analysis and applications.
• Variable time amplitude amplification and quantum algorithms for linear algebra problems

Cited in

(32)

• Variational quantum solutions to the advection-diffusion equation for applications in fluid dynamics
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Enhancing scalability and accuracy of quantum Poisson solver
• Quantum simulation for quantum dynamics with artificial boundary conditions
• Quantum simulation for partial differential equations with physical boundary or interface conditions
• Quantum algorithms for multiscale partial differential equations
• Dense outputs from quantum simulations
• A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations
• Quantum radial basis function method for the Poisson equation
• scientific article; zbMATH DE number 4077891 (Why is no real title available?)
• Energy spectra of the Schrödinger equation and the differential quadrature method
• Existence and uniqueness of solutions of the Koopman-von Neumann equation on bounded domains
• scientific article; zbMATH DE number 4169277 (Why is no real title available?)
• An efficient quantum algorithm for simulating polynomial differential equations
• High-order quantum algorithm for solving linear differential equations
• Time Complexity Analysis of Quantum Difference Methods for Multiscale Transport Equations
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum approach to accelerate finite volume method on steady computational fluid dynamics problems
• Quantum vs. classical algorithms for solving the heat equation
• Towards quantum computational mechanics
• Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion
• Quantum radial basis function method for scattered data interpolation
• Vibration analysis of cyclic symmetrical systems by quantum algorithms
• DSQSS: Discrete space quantum systems solver
• A generalization of Bernstein-Vazirani algorithm with multiple secret keys and a probabilistic oracle
• Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
• Quantum algorithm for the Navier-Stokes equations by using the streamfunction-vorticity formulation and the lattice Boltzmann method
• scientific article; zbMATH DE number 5983594 (Why is no real title available?)
• Quantum computing based state domain equations and feedback control
• Simple digital quantum algorithm for symmetric first-order linear hyperbolic systems

Describes a project that uses

Uses Software

• pchip
• UNCMND

This page was built for publication: Quantum spectral methods for differential equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174656)