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

Zhao Song, Junze Yin, Ruizhe ZhangSubmission to ICLR 2025 · Rejected

TL;DR

Standard quantum algorithms for linear regression promise exponential speedups, but they often hide a catch: their runtimes depend heavily on data-dependent parameters like the condition number $\kappa(A)$, and they output quantum states rather than classical vectors. This paper introduces quantum algorithms for linear, multiple, and ridge regression that output classical solutions and achieve an unconditional quadratic speedup in the dataset size $n$—scaling as $\widetilde{O}(\sqrt{n})$—with absolutely no dependence on condition numbers or matrix-specific parameters.

What Problem Does This Paper Address?

Given a dense matrix $A \in \mathbb{R}^{n \times d}$ and a vector $b \in \mathbb{R}^n$, linear regression seeks a vector $x$ that minimizes $\|Ax - b\|_2^2$ within a relative error $(1 + \epsilon)$. The best classical algorithms solve this via randomized sketching in $O(nd) + \text{poly}(d/\epsilon)$ time, bounded by an $\Omega(n)$ classical barrier to inspect the data.

While quantum linear algebra methods (such as HHL and its descendants) can achieve polylogarithmic dependence on $n$, they introduce major drawbacks:

  1. Data-dependent overhead: Their runtimes scale polynomially with the condition number $\kappa(A)$ (and often Frobenius-to-spectral norm ratios), making them slower than classical algorithms when the data is ill-conditioned.
  2. Quantum state output: They typically prepare the solution as a quantum state $|x\rangle$. Reading out the full classical vector $x \in \mathbb{R}^d$ requires tomography, which adds massive overhead.
  3. De-quantization vulnerabilities: Many quantum-inspired classical algorithms achieve $\text{poly}(\log n)$ runtime if specialized sampling assumptions are met, but they also incur severe polynomial penalties in $\kappa(A)$.

This paper tackles the fundamental question: Can a quantum algorithm solve regression with classical output in $\widetilde{O}_d(\sqrt{n})$ time without depending on matrix condition parameters?

Methods

Rather than relying on quantum linear systems or Hamiltonian simulation, the authors adapt the classical sketch-and-solve paradigm using quantum subroutines:

  1. Leverage Score Sampling via Quantum Routines: In classical sketching, rows of $A$ are sampled proportionally to their leverage scores $\sigma_i = \|U_{i,*}\|_2^2$ (where $U$ is the orthonormal basis of $A$) to form an $\epsilon$-subspace embedding and approximate matrix product. Classically, estimating these scores takes $\Omega(nd)$ time. The authors leverage recent quantum algorithms (by Apers & Gribling, 2023) that estimate leverage scores and sample rows with only $\widetilde{O}(\sqrt{nd})$ row queries using Grover-like amplitude estimation and quantum sampling.
  2. Classical Post-Processing: Once the sketching matrix $S$ subsamples $A$ down to $\widetilde{O}(d/\epsilon)$ rows, the reduced problem $S A x \approx S b$ is solved classically using fast matrix multiplication and pseudoinverse computation, producing a classical vector $x \in \mathbb{R}^d$.
  3. Extension to Multiple and Ridge Regression:
  4. For multiple regression ($B \in \mathbb{R}^{n \times N}$), the same sketch matrix $S$ applies to both $A$ and $B$, followed by fast rectangular matrix multiplication.
  5. For ridge regression, the objective includes a regularization term $\lambda \|x\|_2^2$. The authors analyze the orthonormal basis of the augmented matrix $\tilde{A} = \begin{bmatrix} A \\ \sqrt{\lambda} I_d \end{bmatrix}$ and use quantum leverage score sampling restricted to the first $n$ rows. The sample complexity is bounded by the statistical dimension $\text{sd}_\lambda(A) = \sum_{i=1}^d \frac{1}{1 + \lambda / \sigma_i(A)^2}$.

Datasets

Not discussed in the paper. This is a purely theoretical paper establishing algorithmic runtimes and query complexity bounds; no empirical benchmarks or real-world datasets were evaluated.

Key Insights and Ideas

  • Decoupling Quantum Advantage from Matrix Conditioning: The quadratic speedup in $n$ relies entirely on quantum sampling and leverage score estimation rather than matrix inversion. Because sketching guarantees hold purely from row leverage scores, the condition number $\kappa(A)$ never enters the runtime.
  • Classical Output "for Free": Because quantum speedup is used only for the dimensionality reduction step (sketching $n \to \widetilde{O}(d/\epsilon)$), the final system is solved classically. There is no need for costly quantum state tomography to read out the solution vector $x$.
  • Matching Quantum Lower Bounds: The resulting query complexity of $\widetilde{O}(\sqrt{nd}/\epsilon)$ matches the known quantum query lower bound of $\Omega(\sqrt{n} + d)$ for linear regression with respect to $n$.

Key Results

All algorithms succeed with probability at least $0.999$, outputting classical solutions:

  • Linear Regression:
  • Query complexity: $\widetilde{O}(\sqrt{nd}/\epsilon)$ row queries.
  • Total time: $\widetilde{O}\left(\frac{\sqrt{n} d^{1.5}}{\epsilon} + \frac{d^\omega}{\epsilon}\right)$ (where $\omega \approx 2.37$ is the matrix multiplication exponent).
  • This strictly improves the classical $O(nd) + \text{poly}(d/\epsilon)$ bound with respect to $n$.
  • Multiple Regression ($N$ target columns):
  • Total time: $\widetilde{O}\left(\frac{\sqrt{n} d^{1.5}}{\epsilon} + \frac{d^\omega + N d^{\omega-1}}{\epsilon}\right)$.
  • Ridge Regression:
  • Query complexity: $\widetilde{O}\left(\frac{\sqrt{n \cdot \text{sd}_\lambda(A)}}{\epsilon}\right)$ row queries.
  • Total time: $\widetilde{O}\left(\frac{\sqrt{n \cdot \text{sd}_\lambda(A)} \cdot d}{\epsilon} + \text{poly}(d, \text{sd}_\lambda(A), 1/\epsilon)\right)$.

Limitations and Future Work

  • Dimension Dependence ($d$): While the runtime is sublinear in $n$, it scales polynomially with $d$ ($d^{1.5}$ and $d^\omega$). Thus, quantum advantage is restricted to the "tall and thin" regime where $n \gg d$.
  • Sparsity Constraints: The algorithms assume row-sparse access or coherent quantum query access to the input matrix entries/rows; executing such queries on near-term hardware is challenging without fault-tolerant quantum RAM (QRAM) or efficient oracle circuits.
  • General Regularizers: The current framework applies to $\ell_2$ (ridge) penalties and least-squares objectives; extending parameter-free quadratic speedups to general $\ell_1$ (LASSO), $\ell_p$ regression, or general convex objectives remains open.

Summary updated

Abstract

Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix $A \in \mathbb{R}^{n \times d}$ and a vector $b$, the goal is to find $x'$ such that $\|| Ax' - b \||\_2^2 \leq (1+\epsilon) \min\_{x} \|| A x - b \||\_2^2$. The best classical algorithm takes $O(nd) + \mathrm{poly}(d/\epsilon)$ 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 \emph{Phys. Rev. A 96}, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily{\'e}n 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 $\widetilde{O}(\epsilon^{-1}\sqrt{n}d^{1.5}) + \mathrm{poly}(d/\epsilon)$ time and outputs a classical solution. 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.
BibTeX
@misc{song2023revisiting,
  author = {Zhao Song and Junze Yin and Ruizhe Zhang},
  title = {{Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters}},
  year = {2023},
  eprint = {2311.14823},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.14823},
}
Figure