Enhancing Quantum Linear System Algorithm by Richardson Extrapolation

Abstract

We present a complete implementation of the HHL algorithm to solve tridiagonal Toeplitz systems of linear equations of size N with Ο(log(N)log3(1/ε)+log(κ)λmin/ε) gates, where ε is the accuracy, κ the condition number and λmin the smallest eigenvalue, an exponential improvement in the size of the system over classical methods. In particular, we present efficient oracles for preparing a quantum state where amplitudes are specified by a given function, Hamiltonian simulation and solution observables, and we show that the Euclidean norm of the solution can be obtained deterministically. The main result is the use of Richardson extrapolation for general product formulae Hamiltonian simulation, resulting in an implementation of the quantum phase estimation part at polylog(1/ε) complexity instead of poly(1/ε). For each result we provide detailed mathematical analysis that do not restrict to tridiagonal matrices, and analyze whether it is possible to obtain a quantum advantage taking into account different classes of right hand sides and quantum algorithms. All the procedures presented are implemented with Qiskit and tested on a quantum simulator. We demonstrate our algorithm for a small illustrative problem and two different observables on real hardware of the IBM Quantum Computing Center.