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

boundary value problemCauchy problemChebyshev collocationcomplexitycondition numberlinear ordinary differential equationquantum algorithmsolution errorstate preparation proceduresuccess probability

Mathematics Subject Classification ID

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

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))$.

Review text

In the new and promising realm of quantum computing, the authors formulate and analyze a collocation-type spectral method based on Chebyshev polynomials and Chebyshev-Gauss-Lobatto nodes for solving initial and boundary value problems. The problems are attached to linear systems of differential equations with time-dependent coefficients. The authors provide a quantum algorithm with complexity \(\operatorname{poly}(\log d,\log(1/\varepsilon))\) where \(d\) is the dimension of the system and \(\varepsilon\) stands for solution error. This algorithm seems capable of producing useful information about the final state of the system that cannot be efficiently computed classically. At the end of the paper, relevant comments on some open issues that arise naturally in the context of quantum algorithms are provided.

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

• 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
• 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?)
• 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

(47)

• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Energy spectra of the Schrödinger equation and the differential quadrature method
• Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
• Variational quantum solutions to the advection-diffusion equation for applications in fluid dynamics
• Quantum approach to accelerate finite volume method on steady computational fluid dynamics problems
• Vibration analysis of cyclic symmetrical systems by quantum algorithms
• Simple digital quantum algorithm for symmetric first-order linear hyperbolic systems
• Quantum vs. classical algorithms for solving the heat equation
• Quantum radial basis function method for scattered data interpolation
• A hybrid classical-quantum algorithm for solution of nonlinear ordinary differential equations
• scientific article; zbMATH DE number 5983594 (Why is no real title available?)
• scientific article; zbMATH DE number 4169277 (Why is no real title available?)
• scientific article; zbMATH DE number 4077891 (Why is no real title available?)
• Quantum algorithm for the Navier-Stokes equations by using the streamfunction-vorticity formulation and the lattice Boltzmann method
• Quantum algorithm and circuit design solving the Poisson equation
• High-order quantum algorithm for solving linear differential equations
• Quantum radial basis function method for the Poisson equation
• Time Complexity Analysis of Quantum Difference Methods for Multiscale Transport Equations
• Quantum computing based state domain equations and feedback control
• Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation
• Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion
• DSQSS: Discrete space quantum systems solver
• A generalization of Bernstein-Vazirani algorithm with multiple secret keys and a probabilistic oracle
• Quantum simulation for partial differential equations with physical boundary or interface conditions
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• An efficient quantum algorithm for simulating polynomial differential equations
• Enhancing scalability and accuracy of quantum Poisson solver
• Quantum simulation for quantum dynamics with artificial boundary conditions
• Quantum algorithms for multiscale partial differential equations
• Dense outputs from quantum simulations
• Existence and uniqueness of solutions of the Koopman-von Neumann equation on bounded domains
• Towards quantum computational mechanics
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Numerical solution of nonlinear diffusion-reaction in porous catalysts using quantum spectral successive linearization method
• Solving linear and nonlinear Caputo fractional differential equations with a quantum pseudo-spectral approach
• Computational multiscale methods. Abstracts from the workshop held April 27 -- May 2, 2025
• Quantum circuits for the heat equation with physical boundary conditions via Schrödingerization
• A hybrid quantum-spectral-successive linearization method for general Lane-Emden type equations
• Quantum differential equation solvers: limitations and fast-forwarding
• A quantum approach for optimal control
• Dilation theorem via Schrödingerization, with applications to the quantum simulation of differential equations
• Boundary treatment for variational quantum simulations of partial differential equations on quantum computers
• Quantum simulation of a class of highly-oscillatory transport equations via Schrödingerisation
• Quantum simulation of the Fokker-Planck equation via Schrödingerization
• Quantum spectral method for gradient and Hessian estimation
• Quantum realization of the finite element method
• IQFEM: A quantum finite element method for heterogeneous problems with immersed boundaries

Describes a project that uses

Uses Software

• UNCMND
• pchip

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)