Understand
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 $\|A\vec x - \vec b\|_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.