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

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

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    58 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)1057-1081
    Number of pages25
    JournalCommunications in Mathematical Physics
    Volume356
    Issue number3
    DOIs
    Publication statusPublished - 1 Dec 2017

    Fingerprint

    Dive into the research topics of 'Quantum algorithm for linear differential equations with exponentially improved dependence on precision'. Together they form a unique fingerprint.

    Cite this