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 widetilde O(n0.5dk2.5~poly(ε-1)) for k-median and k-means clustering. Our approach achieves a better dependence on d and constructs smaller coresets that only consist of points in the dataset, compared to recent results of [Xue, Chen, Li and Jiang, ICML'23]. * ℓp regression: For ℓp regression problems, we construct an ε-coreset of size widetilde Op(d^max1, p/2ε-2) in time widetilde Op(n0.5d^max0.5, p/4+1(ε-3+d0.5)), improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for all p∈ (0, 2)cup (2, 22], including the widely studied least absolute deviation regression (ℓ1 regression). * Low-rank approximation with Frobenius norm error: We introduce the first quantum sublinear-time algorithm for low-rank approximation that does not rely on data-dependent parameters, and runs in widetilde O(nd0.5k0.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.