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 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. 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.
Introduction
Linear regression serves as the cornerstone of statistical modeling and machine learning, used extensively to quantify relationships between variables. In the standard setting, we are presented with a dense matrix $A \in \mathbb{R}^{n \times d}$ representing $n$ observations across $d$ features, and a target vector $b \in \mathbb{R}^n$. The objective is to find a coefficient vector $x$ that minimizes the sum of squared residuals.
Classically, solving this problem requires at least $\Omega(nd)$ time, as every entry of the matrix must be inspected. While previous quantum algorithms—most notably those based on the Harrow-Hassidim-Lloyd (HHL) framework—promised exponential speedups, they introduced a significant caveat: their efficiency is tied to the condition number $\kappa(A)$ of the input matrix. For "ill-conditioned" datasets where $\kappa(A)$ is large, these quantum methods can become significantly slower than their classical counterparts. This paper addresses this bottleneck, presenting a quantum algorithm that achieves a provable quadratic speedup in $n$ without any dependence on such data-dependent parameters.
Methodology: Bridging Quantum Sampling and Classical Sketching
The researchers depart from the standard quantum linear algebra paradigm, which often focuses on direct matrix inversion or Hamiltonian simulation. Instead, they leverage techniques from Randomized Numerical Linear Algebra (RandNLA), specifically Leverage Score Sampling and Subspace Embedding.
1. Leverage Score Distribution
Leverage scores are a statistical measure used to identify which rows of a matrix are most influential in determining the overall structure of the row space. By sampling rows according to these scores, one can construct a "sketch"—a much smaller version of the original matrix—that preserves the essential properties of the full dataset.
2. Quantum Speedup for Sampling
The primary innovation lies in the estimation of these leverage scores. The authors utilize a recent quantum routine (Apers and Gribling, 2023) capable of estimating leverage scores in $O(\sqrt{n})$ time. This represents a quadratic improvement over the classical requirement of $O(n)$ to process all rows. By using quantum query access to the rows of $A$, the algorithm identifies the "important" data points significantly faster than any classical observer.
3. The Hybrid Sketching Framework
Once the high-leverage rows are identified via the quantum routine, the algorithm creates a sketched version of the regression problem. This smaller problem is then solved to find the final regression coefficients $x'$. This hybrid approach allows the quantum computer to handle the high-complexity task of data reduction ($n \to \sqrt{n}$), while the final optimization can be handled efficiently using fast matrix multiplication techniques.
Theoretical Results
The paper provides rigorous complexity bounds for three major variations of the regression problem, demonstrating that the speedup is robust across different loss functions and constraints.
- Linear Regression: The proposed algorithm runs in $\tilde{O}(\epsilon^{-1}\sqrt{n}d^{1.5} + d^\omega/\epsilon)$ time. Compared to the classical $O(nd)$ lower bound, this provides a clear quadratic speedup relative to the number of observations $n$.
- Multiple Regression: For problems involving $N$ target variables, the algorithm scales as $\tilde{O}(\epsilon^{-1}\sqrt{n}d^{1.5} + d^\omega/\epsilon + Nd^{\omega-1}/\epsilon)$, maintaining the $\sqrt{n}$ advantage.
- Ridge Regression: In the case of $L_2$-regularized regression, the complexity is tied to the "statistical dimension" $\text{sd}_\lambda(A)$. The algorithm achieves a complexity of $\tilde{O}(\sqrt{n \cdot \text{sd}_\lambda(A)} \cdot d/\epsilon)$. Since the statistical dimension is often much smaller than $d$ in regularized settings, this offers a potent acceleration for high-dimensional problems.
All algorithms are shown to succeed with a high probability (0.999), making them reliable for theoretical and eventually practical applications.
Discussion and Limitations
While this work represents a significant step forward in making quantum machine learning more robust, several considerations remain for future implementation:
- Feature Scaling ($d$): The algorithm's dependence on the number of features $d$ is slightly higher than the best classical algorithms (scaling with $d^{1.5}$ or $d^\omega$ rather than $d$). Consequently, the quantum advantage is most pronounced in "tall and skinny" matrices where the number of observations $n$ vastly exceeds the number of features $d$.
- Sparsity: The current results are optimized for dense matrices. While the authors discuss row sparsity ($r$), further refinements for highly sparse datasets could yield even faster runtimes.
- Hardware and QRAM: Like many algorithms in quantum query complexity, this approach assumes efficient "row query" access to the data. This typically requires a Quantum Random Access Memory (QRAM) architecture, which remains a significant challenge in quantum hardware development.
Conclusion
By marrying quantum sampling techniques with classical sketching theory, this research provides the first unconditional quantum acceleration for linear regression. By removing the dependency on the condition number $\kappa(A)$, the authors have moved quantum linear algebra from a niche tool for well-behaved matrices to a general-purpose accelerator for one of the most fundamental problems in data science.
Summary updated