Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation

Abstract

We present a quantum algorithm to solve systems of linear equations of the form Αx=b, where Α is a tridiagonal Toeplitz matrix and b results from discretizing an analytic function, with a circuit complexity of polylog(κ, 1/ε, N), where N denotes the number of equations, ε the accuracy, and κ the condition number. The repeat-until-success algorithm has to be run Ο(κ/(1-ε)) times to succeed, leveraging amplitude amplification. Thus, the algorithm achieves an exponential improvement with respect to N over classical methods. In particular, we present efficient oracles for state preparation, Hamiltonian simulation and a set of observables together with the corresponding error and complexity analyses. As the main result, we show how to use Richardson extrapolation to enhance Hamiltonian simulation, resulting in an implementation of Quantum Phase Estimation within the algorithm with polylog(1/ε) circuit complexity instead of poly(1/ε). Furthermore, we analyze necessary conditions for the overall algorithm to achieve an exponential speedup compared to classical methods. Our approach can be applied to more general problems where Hamiltonian simulation is approximated via product formulae, although, our theoretical results would need to be extended accordingly.