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+ε) \min_{x} \| A x - b \|_2^2 $. The best classical algorithm takes $O(nd) + \mathrm{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{é}n and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as $κ(A)$, the condition number of $A$. In this work, we develop a quantum algorithm that runs in $\widetilde{O}(ε^{-1}\sqrt{n}d^{1.5}) + \mathrm{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.
Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix A∈Rn×d and a vector b, the goal is to find x′ such that ∥Ax′−b∥22≤(1+ε)minx∥Ax−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{é}n and Jeffery ICALP 2019]. However, the running times of these algorithms depend on some quantum linear algebra-related parameters, such as κ(A), the condition number of A. In this work, we develop a quantum algorithm that runs in O(ε−1nd1.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.
Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector θ∈Rd of coefficients is constrained in either ℓ1-norm (for Lasso) or in ℓ2-norm (for Ridge). We study the complexity of quantum algorithms for finding ε-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of d by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in d, as are the best classical algorithms. As a byproduct of our quantum lower bound for Lasso, we also prove the first classical lower bound for Lasso that is tight up to polylog-factors.
Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector θ ∈ R^d of coefficients is constrained in either ℓ1-norm (for Lasso) or in ℓ2-norm (for Ridge). We study the complexity of quantum algorithms for finding ε-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of d by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in d, as are the best classical algorithms. As a byproduct of our quantum lower bound for Lasso, we also prove the first classical lower bound for Lasso that is tight up to polylog-factors.
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation.Namely, suppose we are given an A∈Cm×n with minimum non-zero singular value σ which supports certain efficient ℓ2 -norm importance sampling queries, along with a b∈Cm . Then, for some x∈Cn satisfying ‖x–A+b‖≤ε‖A+b‖ , we can output a measurement of |x⟩ in the computational basis and output an entry of x with classical algorithms that run in O~(‖A‖F6‖A‖6σ12ε4) and O~(‖A‖F6‖A‖2σ8ε4) time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of ‖A‖16σ16ε2 [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC'20]. 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.
Regression is a cornerstone of statistics and machine learning, with applications spanning science, engineering, and economics. While quantum algorithms for regression have attracted considerable attention, most existing work has focused on linear regression, leaving many more complex yet practically important variants unexplored. In this work, we present a unified quantum framework for accelerating a broad class of regression tasks -- including linear and multiple regression, Lasso, Ridge, Huber, ℓp-, and δp-type regressions -- achieving up to a quadratic improvement in the number of samples m over the best classical algorithms. This speedup is achieved by extending the recent classical breakthrough of Jambulapati et al. (STOC'24) using several quantum techniques, including quantum leverage score approximation (Apers &Gribling, 2024) and the preparation of many copies of a quantum state (Hamoudi, 2022). For problems of dimension n, sparsity r<n, and error parameter ε, our algorithm solves the problem in O(rmn/ε+poly(n,1/ε)) quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where N is the size of the data set, d is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on d and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.
Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle QRAM, the standard model studied in quantum query complexity, requires time O(sqrtn) to encode vectors vinRn into quantum states. We propose simple hardware augmentations to the oracle QRAM, that enable vectors vinRn to be encoded in time O(logn), with pre-processing. The augmented QRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented QRAM for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ketv for AinRmtimesn, the singular value sigmai is estimated within additive error epsilonnormAF. The first algorithm requires time wt1/epsilon3 and uses the approach for simulating e−irho in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time wt1/epsilon and uses Jordan's lemma from linear algebra and the augmented QRAM to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CX and CUR decompositions. Classical algorithms for these problems require time O(mnlogn+poly(1/epsilon)), the quantum algorithms have running time O(sqrtmpoly(1/epsilon,k,Delta)) where k,Delta are the rank and spectral gap. The running time of the quantum CX decomposition algorithm does not depend on m, it is polynomial in problem parameters. We also provide quantum algorithms for ell2 regularized regression problems, the quantum ridge regression algorithm requires time wt1/mu2delta to output a quantum state that is delta close to the solution, where mu is the regularization parameter.