Quantum spectral methods for differential equations

DOI10.1007/S00220-020-03699-ZzbMATH Open1444.81011arXiv1901.00961OpenAlexW3102764375MaRDI QIDQ2174656FDOQ2174656

Jin-Peng Liu, Andrew M. Childs

Publication date: 21 April 2020

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

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

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)

Cites Work

• Title not available (Why is that?)
• Spectral Methods
• Title not available (Why is that?)
• On the relationship between continuous- and discrete-time quantum walk
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Title not available (Why is that?)
• EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS
• A modified spectral method for numerical solution of ordinary differential equations with non-analytic solution
• Title not available (Why is that?)
• Variable time amplitude amplification and quantum algorithms for linear algebra problems
• A modified pseudospectral method for numerical solution of ordinary differential equations systems
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• High-order quantum algorithm for solving linear differential equations

Cited In (23)

• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Quantum algorithm for the Navier–Stokes equations by using the streamfunction-vorticity formulation and the lattice Boltzmann method
• Quantum vs. classical algorithms for solving the heat equation
• 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
• Quantum radial basis function method for scattered data interpolation
• 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
• Title not available (Why is that?)
• Quantum computing based state domain equations and feedback control

Uses Software

• UNCMND
• pchip

   Recommendations

• Spectral methods in computational quantum mechanics 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• 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. 👍 👎

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)