Sublinear Time Quantum Sensitivity Sampling
Organizations: University of California, Berkeley. · Carnegie Mellon University. · Massachusetts Institute of Technology.
Abstract
We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume and, for regression, : - -median/-means: For points in , we build an -coreset of input points of size (resp. ) in time (resp. ). Our better - and linear -dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for (resp. ). - regression: For , , we build an -coreset of size in time for and for , matching [Liu and Ji, ICML'26] for and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all . - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank- approximation of free of data-dependent parameters, running in time with factored output (plus to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity , any quantum algorithm outputting an -coreset of size needs queries, so our query complexity is optimal up to and VC-dimension factors.
Figures & tables
| Weight | Approximation notion | Oracle time | Result |
|---|---|---|---|
| generic sensitivity | -coreset | Theorem C.3 | |
| leverage score | -coreset (spectral) | recovers [ 3 ] | |
| Lewis weight | -approximator (weights) | Theorem C.18 | |
| ridge leverage score | -approximator (add.-mult.) | Corollary D.3 | |
| clustering sensitivity | one-sided only | Theorem H.15 |
Coreset Selection
Coreset selection chooses compact subsets that preserve a dataset’s learning, evaluation, or optimization value while reducing cost.
See all 62 papers