Sublinear Time Quantum Sensitivity Sampling

We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems. Our unified framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation. Our contributions include: * **$k$-median and $k$-means clustering:** For $n$ points in $d$-dimensional Euclidean space, we give an algorithm that constructs an $\epsilon$-coreset in time $\widetilde O(n^{0.5}dk^{2.5}~\mathrm{poly}(\epsilon^{-1}))$ for $k$-median and $k$-means clustering. Our approach achieves a better dependence on $d$ and constructs smaller coresets when $d\gg k$ that only consist of points in the dataset, compared to recent results of [Xue, Chen, Li and Jiang, ICML'23]. * **$\ell_p$ regression:** For $\ell_p$ regression problems $\min_{x\in \mathbb{R}^d}\\|Ax-b\\|_p$ where $A\in \mathbb{R}^{n\times d}$ and $b\in \mathbb{R}^n$, we construct an $\epsilon$-coreset of size $\widetilde O_p(d^{\max\\{1, p/2\\}}\epsilon^{-2})$ in time $\widetilde O_p(n^{0.5}d^{\max\\{0.5, p/4\\}+1}(\epsilon^{-3}+d^{0.5}))$, improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for $p\in (2, 22]$. * **Low-rank approximation with Frobenius norm error:** We introduce the first quantum sublinear-time algorithm for low-rank approximation that approximates the best rank-$k$ solution to a matrix $A\in \mathbb{R}^{d\times n}$ and does not rely on data-dependent parameters, and runs in $\widetilde O(n^{0.5}dk^{0.5}\epsilon^{-1})$ time. Additionally, we present quantum sublinear algorithms for kernel low-rank approximation and tensor low-rank approximation, broadening the range of achievable sublinear time algorithms in randomized numerical linear algebra.