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:2110.13086 · Leibniz international proceedings in informatics

Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

Yanlin Chen, Ronald de Wolf

Published Oct 25, 2021• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.icalp.2023.38

Related papers

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

Quantum Algorithms for the Pathwise Lasso

João Fernando Doriguello, Debbie Lim, Chi Seng Pun +2 more

We present a novel quantum high-dimensional linear regression algorithm with an ℓ1 -penalty based on the classical LARS (Least Angle Regression) pathwise algorithm. Similarly to available classical algorithms for Lasso, our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. A quadratic speedup on the number of features d is possible by using the simple quantum minimum-finding subroutine from Dürr and Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then improve upon this simple quantum algorithm and obtain a quadratic speedup both in the number of features d and the number of observations n by using the approximate quantum minimum-finding subroutine from Chen and de Wolf (ICALP'23). In order to do so, we approximately compute the joining times to be searched over by the approximate quantum minimum-finding subroutine. As another main contribution, we prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm (and therefore our quantum algorithm) is robust to errors. This means that it still outputs a path that minimises the Lasso cost function up to a small error if the joining times are only approximately computed. Furthermore, we show that, when the observations are sampled from a Gaussian distribution, our quantum algorithm's complexity only depends polylogarithmically on n , exponentially better than the classical LARS algorithm, while keeping the quadratic improvement on d . Moreover, we propose a dequantised version of our quantum algorithm that also retains the polylogarithmic dependence on n , albeit presenting the linear scaling on d from the standard LARS algorithm. Finally, we prove query lower bounds for classical and quantum Lasso algorithms.

arXiv:2312.14141•Quantum•Mar 25, 2025•5 citations

Accelerating Regression Tasks with Quantum Algorithms

C. L. Liu, Zhengfeng Ji

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.

arXiv:2509.24757•Sep 29, 2025•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 Differentially Private Sparse Regression Learning

Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu +2 more

The eligibility of various advanced quantum algorithms will be questioned if they can not guarantee privacy. To fill this knowledge gap, here we devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Concretely, given$N~d$-dimensional data points with$N\ll d$, we first prove that the optimal classical and quantum non-private Lasso requires$\Omega (N+d)$and$\Omega (\sqrt {N}+\sqrt {d})$runtime, respectively. We next prove that the runtime cost of QDP Lasso isdimension independent, i.e.,$O(N^{5/2})$, which implies that the QDP Lasso can be faster than both the optimal classical and quantum non-private Lasso. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound$\tilde {O}(N^{-2/3})$with privacy guarantees and discuss the chance to realize it on near-term quantum chips with advantages.

arXiv:2007.11921•IEEE Transactions on Information Theory•Apr 4, 2022•30 citations

On quantum algorithms and limitations for convex optimization and lattice problems

Y. Chen

Optimization is the process of selecting the best option from all possibilities, and problems related to finding the best option among many options are called optimization problems. A few examples of such problems are route picking, partial loading, crew scheduling, and portfolio optimization, and those problems naturally appear everywhere in society and in our daily lives. Most optimization problems could be solved by listing all possibilities and then searching for the best one, but we aim to find a systematic strategy (known as an algorithm) that finds the optimal solution in the least amount of time, as brute-force searching is often too time-consuming. That is, we would like to find optimal algorithms for finding optimal solutions. Quantum physics provides a more accurate explanation and prediction of nature in many cases than classical physics. Therefore, a quantum computer has the potential to be more powerful and useful than a classical one for solving optimization problems, though the extent of this advantage remains an active area of research. Moreover, designing algorithms for a quantum computer requires fundamentally different ideas and concepts than for a classical computer. In this thesis, we explore the uses of quantum computers in solving several fundamental optimization problems. We specifically consider solving linear regression, finding the top eigenvectors of a matrix, and finding the shortest nonzero vector of a lattice. More precisely, we provide near-optimal quantum algorithms that are asymptotically better than the best-possible classical algorithms for linear regression with $\ell_1$-norm constraint (known as Lasso) and for approximating the top eigenvectors of a matrix. Our algorithms for finding the shortest nonzero vector of a lattice are asymptotically better than the best known classical algorithms. On the other hand, there are some problems for which no useful computational advantage is possible, even when we use quantum computers. This situation, however, can sometimes be beneficial if we do not want quantum computers to solve specific problems fast - say, problems relevant to post-quantum cryptography. In such a situation, we would like evidence demonstrating the difficulty of solving these problems on a quantum computer. To this end, we propose variants of Boolean satisfiability problems that are believed to not be more efficiently solvable on a quantum computer, and then via reductions use those (conjectured) quantum lower bounds to study the quantum limitations of several popular optimization problems like lattice problems, quantum strong simulation, and hitting set problems.

•Jan 1, 2024•0 citations
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.
We present a novel quantum high-dimensional linear regression algorithm with an ℓ1 -penalty based on the classical LARS (Least Angle Regression) pathwise algorithm. Similarly to available classical algorithms for Lasso, our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. A quadratic speedup on the number of features d is possible by using the simple quantum minimum-finding subroutine from Dürr and Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then improve upon this simple quantum algorithm and obtain a quadratic speedup both in the number of features d and the number of observations n by using the approximate quantum minimum-finding subroutine from Chen and de Wolf (ICALP'23). In order to do so, we approximately compute the joining times to be searched over by the approximate quantum minimum-finding subroutine. As another main contribution, we prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm (and therefore our quantum algorithm) is robust to errors. This means that it still outputs a path that minimises the Lasso cost function up to a small error if the joining times are only approximately computed. Furthermore, we show that, when the observations are sampled from a Gaussian distribution, our quantum algorithm's complexity only depends polylogarithmically on n , exponentially better than the classical LARS algorithm, while keeping the quadratic improvement on d . Moreover, we propose a dequantised version of our quantum algorithm that also retains the polylogarithmic dependence on n , albeit presenting the linear scaling on d from the standard LARS algorithm. Finally, we prove query lower bounds for classical and quantum Lasso algorithms.
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.
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.
The eligibility of various advanced quantum algorithms will be questioned if they can not guarantee privacy. To fill this knowledge gap, here we devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Concretely, givenN dN~dN d-dimensional data points withN≪dN\ll dN≪d, we first prove that the optimal classical and quantum non-private Lasso requiresΩ(N+d)\Omega (N+d)Ω(N+d)andΩ(N+d)\Omega (\sqrt {N}+\sqrt {d})Ω(N​+d​)runtime, respectively. We next prove that the runtime cost of QDP Lasso isdimension independent, i.e.,O(N5/2)O(N^{5/2})O(N5/2), which implies that the QDP Lasso can be faster than both the optimal classical and quantum non-private Lasso. Last, we exhibit that the QDP Lasso attains a near-optimal utility boundO~(N−2/3)\tilde {O}(N^{-2/3})O~(N−2/3)with privacy guarantees and discuss the chance to realize it on near-term quantum chips with advantages.
Optimization is the process of selecting the best option from all possibilities, and problems related to finding the best option among many options are called optimization problems. A few examples of such problems are route picking, partial loading, crew scheduling, and portfolio optimization, and those problems naturally appear everywhere in society and in our daily lives. Most optimization problems could be solved by listing all possibilities and then searching for the best one, but we aim to find a systematic strategy (known as an algorithm) that finds the optimal solution in the least amount of time, as brute-force searching is often too time-consuming. That is, we would like to find optimal algorithms for finding optimal solutions. Quantum physics provides a more accurate explanation and prediction of nature in many cases than classical physics. Therefore, a quantum computer has the potential to be more powerful and useful than a classical one for solving optimization problems, though the extent of this advantage remains an active area of research. Moreover, designing algorithms for a quantum computer requires fundamentally different ideas and concepts than for a classical computer. In this thesis, we explore the uses of quantum computers in solving several fundamental optimization problems. We specifically consider solving linear regression, finding the top eigenvectors of a matrix, and finding the shortest nonzero vector of a lattice. More precisely, we provide near-optimal quantum algorithms that are asymptotically better than the best-possible classical algorithms for linear regression with ℓ1\ell_1ℓ1​-norm constraint (known as Lasso) and for approximating the top eigenvectors of a matrix. Our algorithms for finding the shortest nonzero vector of a lattice are asymptotically better than the best known classical algorithms. On the other hand, there are some problems for which no useful computational advantage is possible, even when we use quantum computers. This situation, however, can sometimes be beneficial if we do not want quantum computers to solve specific problems fast - say, problems relevant to post-quantum cryptography. In such a situation, we would like evidence demonstrating the difficulty of solving these problems on a quantum computer. To this end, we propose variants of Boolean satisfiability problems that are believed to not be more efficiently solvable on a quantum computer, and then via reductions use those (conjectured) quantum lower bounds to study the quantum limitations of several popular optimization problems like lattice problems, quantum strong simulation, and hitting set problems.