# Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

arXiv: https://arxiv.org/abs/2110.13086 · HTML: https://mlsanity.com/paper/2110.13086/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 52 references that are in the map.
- First posted on arXiv 25 Oct 2021.

## Builds on (most cited first, 16 of 16)

- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension](https://mlsanity.com/paper/1811.04909/) (2018)
- [Quantum Differentially Private Sparse Regression Learning](https://mlsanity.com/paper/2007.11921/) (2020)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [Quantum algorithms for escaping from saddle points](https://mlsanity.com/paper/2007.10253/) (2020)
- [Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving](https://mlsanity.com/paper/1911.07306/) (2019)
- [Quantum Boosting](https://mlsanity.com/paper/2002.05056/) (2020)
- [Improved Quantum Boosting](https://mlsanity.com/paper/2009.08360/) (2020)
- [No quantum speedup over gradient descent for non-smooth convex optimization](https://mlsanity.com/paper/2010.01801/) (2020)
- [An Equivalence between the Lasso and Support Vector Machines](https://mlsanity.com/paper/1303.1152/) (2013)
- [Quantum Sparse Support Vector Machines](https://mlsanity.com/paper/1902.01879/) (2019)
- [Quantum algorithms for matrix scaling and matrix balancing](https://mlsanity.com/paper/2011.12823/) (2020)
- [Improved quantum lower and upper bounds for matrix scaling](https://mlsanity.com/paper/2109.15282/) (2021)

## Built on by (most cited first, 11 of 11)

- [Improved machine learning algorithm for predicting ground state properties](https://mlsanity.com/paper/2301.13169/) (2023)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Quantum Algorithms for the Pathwise Lasso](https://mlsanity.com/paper/2312.14141/) (2023)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit](https://mlsanity.com/paper/2510.06925/) (2025)
- [Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model](https://mlsanity.com/paper/2608.02826/) (2026)

## Abstract (arXiv)

Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector θ∈ℝ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 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.