Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.24757

Accelerating Regression Tasks with Quantum Algorithms

C. L. Liu, Zhengfeng Ji

Published Sep 29, 2025• 0 citations
arXivHTMLPDF

Abstract

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, $\ell_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 $\widetilde{O}(r\sqrt{mn}/ε+ \mathrm{poly}(n,1/ε))$ quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.

DOI
10.48550/arxiv.2509.24757

Related papers

Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

Yanlin Chen, Ronald de Wolf

Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector $θ\in\mathbb{R}^d$ of coefficients is constrained in either $\ell_1$-norm (for Lasso) or in $\ell_2$-norm (for Ridge). We study the complexity of quantum algorithms for finding $\varepsilon$-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.

arXiv:2110.13086•Leibniz international proceedings in informatics•Oct 25, 2021•5 citations

Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

Chen, Y., Ronald de Wolf

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.

•Jul 1, 2023•0 citations

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

Zhao Song, Junze Yin, Ruizhe Zhang

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.

arXiv:2311.14823•Nov 24, 2023•0 citations

Quantum-enhanced Regression Analysis Using State-of-the-art QLSAs and QIPMs

Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Brandon Augustino +2 more

Quantum computing has the potential to speed up machine learning methods. One major direction is using quantum linear algebra to solve linear system problems or optimization problems in the machine learning area. Quantum approaches in the literature for different types of least squares problems demonstrate speedups w.r.t. dimension but have disadvantages w.r.t. precision and condition number. In this paper, we discuss how an iterative refinement scheme can deliver an accurate solution without the excessive cost of Quantum Linear System Algorithms (QLSAs). In addition, we propose an adaptive regularization approach that can mitigate the effect of condition number on solution time. In the second part of this paper, we investigate how state-of-the-art Quantum Interior Point Methods (QIPMs) can solve more sophisticated regression problems such as Lasso regression and support vector machine problems, which can be reformulated as quadratic optimization problems.

IEEE/ACM Symposium on Edge Computing (SEC)•Dec 1, 2022•5 citations

Sublinear Time Quantum Sensitivity Sampling

Zhao Song, David Paul Woodruff, Lichen Zhang

We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems. Our unified framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation. Our contributions include: * $k$-median and $k$-means clustering: For $n$ points in $d$-dimensional Euclidean space, we give an algorithm that constructs an $ε$-coreset in time $\widetilde O(n^{0.5}dk^{2.5}~\mathrm{poly}(ε^{-1}))$ for $k$-median and $k$-means clustering. Our approach achieves a better dependence on $d$ and constructs smaller coresets that only consist of points in the dataset, compared to recent results of [Xue, Chen, Li and Jiang, ICML'23]. * $\ell_p$ regression: For $\ell_p$ regression problems, we construct an $ε$-coreset of size $\widetilde O_p(d^{\max\{1, p/2\}}ε^{-2})$ in time $\widetilde O_p(n^{0.5}d^{\max\{0.5, p/4\}+1}(ε^{-3}+d^{0.5}))$, improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for all $p\in (0, 2)\cup (2, 22]$, including the widely studied least absolute deviation regression ($\ell_1$ regression). * Low-rank approximation with Frobenius norm error: We introduce the first quantum sublinear-time algorithm for low-rank approximation that does not rely on data-dependent parameters, and runs in $\widetilde O(nd^{0.5}k^{0.5}ε^{-1})$ time. Additionally, we present quantum sublinear algorithms for kernel low-rank approximation and tensor low-rank approximation, broadening the range of achievable sublinear time algorithms in randomized numerical linear algebra.

arXiv:2509.16801•Sep 20, 2025•0 citations

Quantum speedup of leverage score sampling and its application

Changpeng Shao

Leverage score sampling is crucial to the design of randomized algorithms for large-scale matrix problems, while the computation of leverage scores is a bottleneck of many applications. In this paper, we propose a quantum algorithm to accelerate this useful method. The speedup is at least quadratic and could be exponential for well-conditioned matrices. We also prove some quantum lower bounds, which suggest that our quantum algorithm is close to optimal. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs. It achieves polynomial speedups over the best classical algorithm known. In this process, we give an improved randomized algorithm for rigid regression.

arXiv:2301.06107•Jan 15, 2023•1 citation
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\ell_pℓp​-, and δpδ_pδp​-type regressions -- achieving up to a quadratic improvement in the number of samples mmm 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 nnn, sparsity r<nr < nr<n, and error parameter εεε, our algorithm solves the problem in O~(rmn/ε+poly(n,1/ε))\widetilde{O}(r\sqrt{mn}/ε+ \mathrm{poly}(n,1/ε))O(rmn​/ε+poly(n,1/ε)) quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.
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θ\in\mathbb{R}^dθ∈Rd of coefficients is constrained in either ℓ1\ell_1ℓ1​-norm (for Lasso) or in ℓ2\ell_2ℓ2​-norm (for Ridge). We study the complexity of quantum algorithms for finding ε\varepsilonε-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of ddd by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in ddd, 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.
Linear regression is one of the most fundamental linear algebra problems. Given a dense matrix A∈Rn×dA \in \mathbb{R}^{n \times d}A∈Rn×d and a vector bbb, the goal is to find x′x'x′ such that $ \| Ax' - b \|_2^2 \leq (1+ε) \min_{x} \| A x - b \|_2^2 $. The best classical algorithm takes O(nd)+poly(d/ε)O(nd) + \mathrm{poly}(d/ε)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)κ(A)κ(A), the condition number of AAA. In this work, we develop a quantum algorithm that runs in O~(ε−1nd1.5)+poly(d/ε)\widetilde{O}(ε^{-1}\sqrt{n}d^{1.5}) + \mathrm{poly}(d/ε)O(ε−1n​d1.5)+poly(d/ε) time. It provides a quadratic quantum speedup in nnn 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.
Quantum computing has the potential to speed up machine learning methods. One major direction is using quantum linear algebra to solve linear system problems or optimization problems in the machine learning area. Quantum approaches in the literature for different types of least squares problems demonstrate speedups w.r.t. dimension but have disadvantages w.r.t. precision and condition number. In this paper, we discuss how an iterative refinement scheme can deliver an accurate solution without the excessive cost of Quantum Linear System Algorithms (QLSAs). In addition, we propose an adaptive regularization approach that can mitigate the effect of condition number on solution time. In the second part of this paper, we investigate how state-of-the-art Quantum Interior Point Methods (QIPMs) can solve more sophisticated regression problems such as Lasso regression and support vector machine problems, which can be reformulated as quadratic optimization problems.
We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems. Our unified framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation. Our contributions include: * kkk-median and kkk-means clustering: For nnn points in ddd-dimensional Euclidean space, we give an algorithm that constructs an εεε-coreset in time O~(n0.5dk2.5 poly(ε−1))\widetilde O(n^{0.5}dk^{2.5}~\mathrm{poly}(ε^{-1}))O(n0.5dk2.5 poly(ε−1)) for kkk-median and kkk-means clustering. Our approach achieves a better dependence on ddd and constructs smaller coresets that only consist of points in the dataset, compared to recent results of [Xue, Chen, Li and Jiang, ICML'23]. * ℓp\ell_pℓp​ regression: For ℓp\ell_pℓp​ regression problems, we construct an εεε-coreset of size O~p(dmax⁡{1,p/2}ε−2)\widetilde O_p(d^{\max\{1, p/2\}}ε^{-2})Op​(dmax{1,p/2}ε−2) in time O~p(n0.5dmax⁡{0.5,p/4}+1(ε−3+d0.5))\widetilde O_p(n^{0.5}d^{\max\{0.5, p/4\}+1}(ε^{-3}+d^{0.5}))Op​(n0.5dmax{0.5,p/4}+1(ε−3+d0.5)), improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for all p∈(0,2)∪(2,22]p\in (0, 2)\cup (2, 22]p∈(0,2)∪(2,22], including the widely studied least absolute deviation regression (ℓ1\ell_1ℓ1​ regression). * Low-rank approximation with Frobenius norm error: We introduce the first quantum sublinear-time algorithm for low-rank approximation that does not rely on data-dependent parameters, and runs in O~(nd0.5k0.5ε−1)\widetilde O(nd^{0.5}k^{0.5}ε^{-1})O(nd0.5k0.5ε−1) time. Additionally, we present quantum sublinear algorithms for kernel low-rank approximation and tensor low-rank approximation, broadening the range of achievable sublinear time algorithms in randomized numerical linear algebra.
Leverage score sampling is crucial to the design of randomized algorithms for large-scale matrix problems, while the computation of leverage scores is a bottleneck of many applications. In this paper, we propose a quantum algorithm to accelerate this useful method. The speedup is at least quadratic and could be exponential for well-conditioned matrices. We also prove some quantum lower bounds, which suggest that our quantum algorithm is close to optimal. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs. It achieves polynomial speedups over the best classical algorithm known. In this process, we give an improved randomized algorithm for rigid regression.