Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision

By Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, Guoming Wang. Communications in Mathematical Physics, 2017

303 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/c6d28464fcbc1d88c03279f48a85b051c918a8ad

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Efficient quantum algorithm for dissipative nonlinear differential equations (2020, background): “As discussed in Section 1, it is challenging to directly simulate quadratic ODEs using quantum computers, and indeed the complexity of the best known quantum algorithm is exponential in the evolution time T [39].”