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 (40)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• Error mitigation for short-depth quantum circuits
• Extending the computational reach of a noisy superconducting quantum processor
• Exponential algorithmic speedup by quantum walk
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Data Fitting
• On the relationship between continuous- and discrete-time quantum walk
• Cloud Quantum Computing of an Atomic Nucleus
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Mitigating measurement errors in multi-qubit experiments
• Quantum-state preparation with universal gate decompositions
• Preconditioned quantum linear system algorithm
• Quantum Risk Analysis
• Prediction by linear regression on a quantum computer
• Creating superpositions that correspond to efficiently integrable probability distributions
• A quantum-inspired classical algorithm for recommendation systems
• A quantum linear system algorithm for dense matrices
• Quantum Circuits for Isometries
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum algorithms and the finite element method
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum-inspired algorithms in practice
• Efficient Scheme for Initializing a Quantum Register with an Arbitrary Superposed State
• Characterization of a two-transmon processor with individual single-shot qubit readout
• Quantum assisted Gaussian process regression
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Simulating sparse Hamiltonians with star decompositions
• Mitigating algorithmic errors in Hamiltonian simulation
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Efficient State Preparation for Quantum Amplitude Estimation
• Optimizing Quantum Circuits for Arithmetic
• Quantum Circulant Preconditioner for Linear System of Equations
• Quantum Mechanics, Path Integrals and Option Pricing: Reducing the Complexity of Finance
• Well-conditioned multiproduct Hamiltonian simulation
• Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions
• Initializing the Amplitude Distribution of a Quantum State

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