Quantum algorithm for linear differential equations with exponentially improved dependence on precision

Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, Guoming Wang

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.

LanguageEnglish
Pages1057-1081
Number of pages25
JournalCommunications in Mathematical Physics
Volume356
Issue number3
DOIs
Publication statusPublished - 1 Dec 2017

Fingerprint

Quantum Algorithms
Linear differential equation
differential equations
Linear Systems
linear systems
Linear Ordinary Differential Equations
Taylor series
Numerical Stability
Quantum State
Propagator
Logarithm
Quantum Systems
Difference Method
Finite Difference
Encoding
Directly proportional
numerical stability
logarithms
Polynomial
Coefficient

Cite this

@article{10559c585d59490187a42f175c0d0637,
title = "Quantum algorithm for linear differential equations with exponentially improved dependence on precision",
abstract = "We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.",
author = "Berry, {Dominic W.} and Childs, {Andrew M.} and Aaron Ostrander and Guoming Wang",
year = "2017",
month = "12",
day = "1",
doi = "10.1007/s00220-017-3002-y",
language = "English",
volume = "356",
pages = "1057--1081",
journal = "Communications in Mathematical Physics",
issn = "0010-3616",
publisher = "Springer, Springer Nature",
number = "3",

}

Quantum algorithm for linear differential equations with exponentially improved dependence on precision. / Berry, Dominic W.; Childs, Andrew M.; Ostrander, Aaron; Wang, Guoming.

In: Communications in Mathematical Physics, Vol. 356, No. 3, 01.12.2017, p. 1057-1081.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Quantum algorithm for linear differential equations with exponentially improved dependence on precision

AU - Berry, Dominic W.

AU - Childs, Andrew M.

AU - Ostrander, Aaron

AU - Wang, Guoming

PY - 2017/12/1

Y1 - 2017/12/1

N2 - We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.

AB - We present a quantum algorithm for systems of (possibly inhomogeneous) linear ordinary differential equations with constant coefficients. The algorithm produces a quantum state that is proportional to the solution at a desired final time. The complexity of the algorithm is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. Our result builds upon recent advances in quantum linear systems algorithms by encoding the simulation into a sparse, well-conditioned linear system that approximates evolution according to the propagator using a Taylor series. Unlike with finite difference methods, our approach does not require additional hypotheses to ensure numerical stability.

UR - http://www.scopus.com/inward/record.url?scp=85030661144&partnerID=8YFLogxK

U2 - 10.1007/s00220-017-3002-y

DO - 10.1007/s00220-017-3002-y

M3 - Article

VL - 356

SP - 1057

EP - 1081

JO - Communications in Mathematical Physics

T2 - Communications in Mathematical Physics

JF - Communications in Mathematical Physics

SN - 0010-3616

IS - 3

ER -