Quantum Lasso: Closing the Gap in High Dimensions via Adaptive Frank–Wolfe

We study Lasso, a linear regression problem that minimizes the mean squared loss subject to the coefficient vector having ${\ell }_1$-norm at most one. We use quantum queries to data entries on index superpositions. chen2023 (CdW) use approximate quantum minimum finding with additive error $O(ϵ)$ for Frank–Wolfe direction selection. Each update costs $\text{wtO}(\sqrt{d}/ϵ)$ queries, leaving a gap to the high-dimensional lower bound. We propose a new algorithm, Adaptive Quantum Frank–Wolfe (AQFW), which returns an explicit feasible $O(1/ϵ)$-sparse $ϵ$-optimal vector with constant confidence using $\text{wtO}(\sqrt{d}{ϵ}^{-3/2}+{ϵ}^{-2})$ queries. For $d\gtrsim 1/ϵ$ and $N\gtrsim {ϵ}^{-2}\log d$, this improves CdW's bound by ${ϵ}^{-1/2}$ and matches their lower bound up to logarithms. AQFW replaces $ϵ$-precision minimum finding with randomized threshold searches that test estimated loss-decrease slopes along signed coordinate directions (atoms). Smaller thresholds require more precise, costlier estimates, so we reduce Grover iteration caps, where each attempt costs $\text{wtO}(\sqrt{d/ϵ}+{ϵ}^{-1})$ queries, cheaper than CdW's $\text{wtO}(\sqrt{d}/ϵ)$. Accepted step sizes are proportional to the threshold, ensuring sufficient loss decrease under accurate checks. A simplex lift represents $\theta$ by a distribution $q$ over atoms. Mixing $q$ with the uniform distribution reuses information and warm-starts searches while keeping every atom accessible. We propose a multiplicative potential that combines the objective suboptimality gap with an exponentiated Kullback–Leibler (KL) divergence from a fixed optimal atom distribution to the current one. Our analysis shows that $\text{wtO}({ϵ}^{-1})$ searches suffice to reach $ϵ$-accuracy, matching the baseline's $O({ϵ}^{-1})$ searches up to logarithms. Finite-precision state preparation preserves the bound.