Accelerating Regression Tasks with Quantum 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, $\ell_p$-, and $\delta_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 a non-trivial quantization of the recent classical breakthrough of Jambulapati et al. (2024), where we construct a full quantum pipeline that strategically employs quantum leverage score approximation to initialize and refine Multiscale Leverage Score Overestimates, enabling efficient importance sampling via the preparation of multiple state copies. For problems of dimension $n$, sparsity $r < n$, and error parameter $\epsilon$, our algorithm solves the problem in $\widetilde{O}(r\sqrt{mn}/\epsilon + \mathrm{poly}(n,1/\epsilon))$ quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.