Improving quantum linear system solvers via a gradient descent perspective

Abstract

Solving systems of linear equations is one of the most important primitives in quantum computing that has the potential to provide a practical quantum advantage in many different areas, including in optimization, simulation, and machine learning. In this work, we revisit quantum linear system solvers from the perspective of convex optimization, and in particular gradient descent-type algorithms. This leads to a considerable constant-factor improvement in the runtime (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth). More precisely, we first show how the asymptotically optimal quantum linear system solver of Childs, Kothari, and Somma is related to the gradient descent algorithm on the convex function $\Vert A\vec{x}-\vec{b}{\Vert }_2^2$: their linear system solver is based on a truncation in the Chebyshev basis of the degree-$(t-1)$ polynomial (in $A$) that maps the initial solution ${\vec{x}}_1:=\vec{b}$ to the $t$-th iterate ${\vec{x}}_t$ in the basic gradient descent algorithm. Then, instead of starting from the basic gradient descent algorithm, we use the optimal Chebyshev iteration method (which can be viewed as an accelerated gradient descent algorithm) and show that this leads to considerable improvements in the quantum solver.

References in corpus (12)

• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A Grand Unification of Quantum Algorithms
• Quantum gradient descent for linear systems and least squares
• Efficient phase-factor evaluation in quantum signal processing
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Hamiltonian Simulation by Uniform Spectral Amplification
• Finding Angles for Quantum Signal Processing with Machine Precision
• Quantum vs. classical algorithms for solving the heat equation
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number