An improved quantum-inspired algorithm for linear regression

Abstract

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 $\Vert x-A^{+}b\Vert \le \epsilon \Vert A^{+}b\Vert$, we can output a measurement of $|x⟩$ in the computational basis and output an entry of $x$ with classical algorithms that run in $\tilde{\mathcal{O}}\left(\frac{\Vert A{\Vert }_{\mathrm{F}}^6\Vert A{\Vert }^6}{{\sigma }^{12}{\epsilon }^4}\right)$ and $\tilde{\mathcal{O}}\left(\frac{\Vert A{\Vert }_{\mathrm{F}}^6\Vert A{\Vert }^2}{{\sigma }^8{\epsilon }^4}\right)$ time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of $\frac{\Vert A{\Vert }^{16}}{{\sigma }^{16}{\epsilon }^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.

21 pages, v4 journal version, v2 bug fixed

References in corpus (3)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Sketching as a Tool for Numerical Linear Algebra

Cited by in corpus (16)

• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Biology and medicine in the landscape of quantum advantages
• Prospects and challenges of quantum finance
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum Regularized Least Squares
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Low-depth Clifford circuits approximately solve MaxCut
• Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• Quantum Computing for Data Centric Engineering and Science
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum-Inspired Classical Algorithm for Slow Feature Analysis
• Lower bounds for quantum-inspired classical algorithms via communication complexity
• Fermionic Machine Learning
• Benchmarking of quantum fidelity kernels for Gaussian process regression