{"ID":2868496,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.16801","arxiv_id":"2509.16801","title":"Sublinear Time Quantum Sensitivity Sampling","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 $\\widetilde O(n^{0.5}dk^{2.5}~\\mathrm{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]. * $\\ell_p$ regression: For $\\ell_p$ regression problems, we construct an $ε$-coreset of size $\\widetilde O_p(d^{\\max\\{1, p/2\\}}ε^{-2})$ in time $\\widetilde O_p(n^{0.5}d^{\\max\\{0.5, p/4\\}+1}(ε^{-3}+d^{0.5}))$, improving upon the prior best quantum sampling approach of [Apers and Gribling, QIP'24] for all $p\\in (0, 2)\\cup (2, 22]$, including the widely studied least absolute deviation regression ($\\ell_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(nd^{0.5}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.","short_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 cluster...","url_abs":"https://arxiv.org/abs/2509.16801","url_pdf":"https://arxiv.org/pdf/2509.16801v1","authors":"[\"Zhao Song\",\"David P. Woodruff\",\"Lichen Zhang\"]","published":"2025-09-20T20:18:49Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"quant-ph\"]","methods":"[]","has_code":false}