# An improved quantum-inspired algorithm for linear regression

arXiv: https://arxiv.org/abs/2009.07268 · HTML: https://mlsanity.com/paper/2009.07268/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2020.

## Built on by (most cited first, 8 of 8)

- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms](https://mlsanity.com/paper/2304.04932/) (2023)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [HHL with a Coherent Fourier Oracle: A Proof-of-Concept Quantum Architecture for Joint Melody-Harmony Generation](https://mlsanity.com/paper/2604.20882/) (2026)

## Abstract (arXiv)

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 ∈ mathbbCm× n with minimum non-zero singular value σ which supports certain efficient ℓ2-norm importance sampling queries, along with a b ∈ mathbbCm. Then, for some x ∈ mathbbCn satisfying |x - A^+b| ≤ 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 tildeObig(frac|A|F6|A|6σ12varepsilon4big) and tildeObig(frac|A|F6|A|2σ8varepsilon4big) time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of frac|A|16σ16varepsilon2 [Chia, Gily'en, 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.