An improved quantum-inspired algorithm for linear regression

• Published in: arXiv.org 2022-06
• Main Authors: Gilyén, András, Zhao, Song, Tang, Ewin
• Format: Article
• Language: English
• Subjects: Algorithms; Computer simulation; Data structures; Importance sampling; Mathematical analysis; Matrix methods; Quantum computers; Regression analysis
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2009.07268

We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09, arXiv:0811.3171] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18, arXiv:1704.06174], 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}^{m\times 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 \(|x\rangle\) 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^8\varepsilon^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, arXiv:1910.06151]. 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.