About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
APS March Meeting 2020
Talk
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.