An improved quantum algorithm for low-rank rigid linear regressions with vector solution outputs

Let $A\in \mathbb{R}^{n\times d}, \b \in \mathbb{R}^{n}$ and $\lambda>0$, for rigid linear regression \[ \argmin_{\x} \quad Z(\x) = \|A\x-\b\|^2 + \lambda^2 \|\x\|^2, \] we propose a quantum algorithm, in the framework of block-encoding, that returns a vector solution $\tilde{\x}_{\rm opt}$ such that $Z(\tilde{\x}_{\rm opt}) \leq (1+\varepsilon) Z(\x_{\rm opt})$, where $\x_{\rm opt}$ is an optimal solution. If a block-encoding of $A$ is constructed in time $O(T)$, then the cost of the quantum algorithm is roughly $\widetilde{O}(\K \sqrt{d}/\varepsilon^{1.5} + d/\varepsilon)$ when $A$ is low-rank and $n=\widetilde{O}(d)$. Here $\K=T\alpha/\lambda$ and $\alpha$ is a normalization parameter such that $A/\alpha$ is encoded in a unitary through the block-encoding. This can be more efficient than naive quantum algorithms using quantum linear solvers and quantum tomography or amplitude estimation, which usually cost $\widetilde{O}(\K d/\varepsilon)$. The main technique we use is a quantum accelerated version of leverage score sampling, which may have other applications. The speedup of leverage score sampling can be quadratic or even exponential in certain cases. As a byproduct, we propose an improved randomized classical algorithm for rigid linear regressions. Finally, we show some lower bounds on performing leverage score sampling and solving linear regressions on a quantum computer.