Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation

Abstract

We present a quantum algorithm to solve systems of linear equations of the form $A\mathbf{x}=\mathbf{b}$, where $A$ is a tridiagonal Toeplitz matrix and $\mathbf{b}$ results from discretizing an analytic function, with a circuit complexity of $poly(\log (\kappa ),1/\sqrt{\epsilon },\log (N))$, where $N$ denotes the number of equations, $\epsilon$ is the accuracy, and $\kappa$ the condition number. The \emph{repeat-until-success} algorithm has to be run $\mathcal{O}\left(\kappa /(1-\epsilon )\right)$ times to succeed, leveraging amplitude amplification, and sampled $\mathcal{O}(1/{\epsilon }^2)$ times. 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 of this work, we show how to use Richardson extrapolation to enhance Hamiltonian simulation, resulting in an implementation of Quantum Phase Estimation (QPE) within the algorithm with $1/\sqrt{\epsilon }$ circuit complexity instead of $1/\epsilon$ and which can be parallelized. Furthermore, we analyze necessary conditions for the overall algorithm to achieve an exponential speedup compared to classical methods. Our approach is not limited to the considered setting and 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. All the procedures presented are implemented with Qiskit and tested for small systems using classical simulation as well as using real quantum devices available through the IBM Quantum Experience.

25 pages, 15 figures

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Exponential algorithmic speedup by quantum walk
• Quantum Data Fitting
• Quantum-state preparation with universal gate decompositions
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum algorithm and circuit design solving the Poisson equation
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Simulating sparse Hamiltonians with star decompositions
• Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions

Cited by in corpus (19)

• Quantum Error Mitigation
• Solving nonlinear differential equations with differentiable quantum circuits
• Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
• Hybrid quantum algorithms for flow problems
• A variational quantum algorithm for the Feynman-Kac formula
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• A Performance Study of Variational Quantum Algorithms for Solving the Poisson Equation on a Quantum Computer
• Towards Quantum Computational Mechanics
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Simulating fluid flows with quantum computing
• Compact quantum algorithms for time-dependent differential equations
• Quantum Power Flows: From Theory to Practice
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• Identifying Bottlenecks of NISQ-friendly HHL algorithms
• Improved resource-tunable near-term quantum algorithms for transition probabilities, with applications in physics and variational quantum linear algebra
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• On the commutator scaling in Hamiltonian simulation with multi-product formulas
• QAFE${}^2$: Quantum accelerated multiscale finite element analysis