mlsanityData to 7 Oct 2026

Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters

arXiv 2311.14823 ↗First posted 24 Nov 2023quant-ph cs.DS cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix A ∈ ℝn × d and a vector b, the goal is to find x' such that | Ax' - b |22 ≤ (1+ε) minx | A x - b |22 . The best classical algorithm takes O(nd) + poly(d/ε) time [Clarkson and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013]. On the other hand, quantum linear regression algorithms can achieve exponential quantum speedups, as shown in [Wang Phys. Rev. A 96, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily'en and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as kappa(A), the condition number of A. In this work, we develop a quantum algorithm that runs in widetildeO(ε-1√nd1.5) + poly(d/ε) time. It provides a quadratic quantum speedup in n over the classical lower bound without any dependence on data-dependent parameters. In addition, we also show our result can be generalized to multiple regression and ridge linear regression.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 15 of its 55 references that are in the map. First posted on arXiv 24 Nov 2023.

Builds on

15 of 55 references.

References · 15

  1. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  2. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
  3. 2016Quantum Recommendation Systemscited by 69
  4. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  5. 2017Relative Error Tensor Low Rank Approximationcited by 45
  6. 2019Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learningcited by 37
  7. 2023New Bounds for Matrix Multiplication: from Alpha to Omegacited by 34
  8. 2018The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulationcited by 30
  9. 2016Sharper Bounds for Regularized Data Fittingcited by 19
  10. 2022Faster Matrix Multiplication via Asymmetric Hashingcited by 19
  11. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  12. 2021Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraintscited by 11
3 more
  1. 2020An improved quantum-inspired algorithm for linear regressioncited by 8
  2. 2015Feature Selection for Ridge Regression with Provable Guaranteescited by 5
  3. 2023Faster Rectangular Matrix Multiplication by Combination Loss Analysiscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 4; 2025: 3.

7 papers.

  1. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  2. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  3. 2024How to Inverting the Leverage Score Distribution?cited by 5
  4. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  5. 2024Inverting the Leverage Score Gradient: An Efficient Approximate Newton Methodcited by 3
  6. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  7. 2024Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descentcited by 0