Abstract
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 O(n^0.5dk^2.5 poly(ε⁻¹)) 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 O_p(d^max{1, p/2}ε⁻²) in time O_p(n^0.5d^max{0.5, p/4}+1(ε⁻³+d^0.5)), improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for all p∈ (0, 2)∪ (2, 22], including the widely studied least absolute deviation regression (ℓ₁ 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 O(nd^0.5k^0.5ε⁻¹) 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.