An improved quantum-inspired algorithm for linear regression

Quantum 6, 754 (2022).

https://doi.org/10.22331/q-2022-06-30-754

We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters’09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters’18], when the input matrix $A$ is stored in a data structure applicable for QRAM-based state preparation.

Namely, suppose we are given an $A in mathbb{C}^{mtimes n}$ with minimum non-zero singular value $sigma$ which supports certain efficient $ell_2$-norm importance sampling queries, along with a $b in mathbb{C}^m$. Then, for some $x in mathbb{C}^n$ satisfying $|x – A^+b| leq varepsilon|A^+b|$, we can output a measurement of $|xrangle$ in the computational basis and output an entry of $x$ with classical algorithms that run in $tilde{mathcal{O}}big(frac{|A|_{mathrm{F}}^6|A|^6}{sigma^{12}varepsilon^4}big)$ and $tilde{mathcal{O}}big(frac{|A|_{mathrm{F}}^6|A|^2}{sigma^8varepsilon^4}big)$ time, respectively. This improves on previous “quantum-inspired” algorithms in this line of research by at least a factor of $frac{|A|^{16}}{sigma^{16}varepsilon^2}$ [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC’20]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.