Abstract

We present a novel quantum high-dimensional linear regression algorithm withan $\ell_1$-penalty based on the classical LARS (Least Angle Regression)pathwise algorithm. Similarly to available classical algorithms for Lasso, ourquantum algorithm provides the full regularisation path as the penalty termvaries, but quadratically faster per iteration under specific conditions. Aquadratic speedup on the number of features $d$ is possible by using the simplequantum minimum-finding subroutine from D\"urr and Hoyer (arXiv'96) in order toobtain the joining time at each iteration. We then improve upon this simplequantum algorithm and obtain a quadratic speedup both in the number of features$d$ and the number of observations $n$ by using the approximate quantumminimum-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 theapproximate 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 toerrors. This means that it still outputs a path that minimises the Lasso costfunction up to a small error if the joining times are only approximatelycomputed. Furthermore, we show that, when the observations are sampled from aGaussian distribution, our quantum algorithm's complexity only dependspolylogarithmically on $n$, exponentially better than the classical LARSalgorithm, while keeping the quadratic improvement on $d$. Moreover, we proposea dequantised version of our quantum algorithm that also retains thepolylogarithmic dependence on $n$, albeit presenting the linear scaling on $d$from the standard LARS algorithm. Finally, we prove query lower bounds forclassical and quantum Lasso algorithms.