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 $ϵ$-coreset in time $\tilde{O}(n^{0.5}d{k}^{2.5}\mathrm{poly}({ϵ}^{-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 $$\begin{gathered} {\min }_{x\in {\mathbb{R}}^d} \\ |Ax-b \\ {|}_p \end{gathered}$$ where $A\in {\mathbb{R}}^{n\times d}$ and $b\in {\mathbb{R}}^n$, we construct an $ϵ$-coreset of size $$\begin{gathered} {\tilde{O}}_p(d^{\max \\ 1,p/2 \\ }{ϵ}^{-2}) \end{gathered}$$ in time $$\begin{gathered} {\tilde{O}}_p(n^{0.5}{d}^{\max \\ 0.5,p/4 \\ +1}({ϵ}^{-3}+d^{0.5})) \end{gathered}$$, 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 $\tilde{O}(n^{0.5}d{k}^{0.5}{ϵ}^{-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.