Near-Optimal Quantum Coreset Construction Algorithms for Clustering
This addresses the open problem of quantum speedups for clustering, offering near-optimal algorithms with potential applications in quantum machine learning, though it is incremental as it builds on classical coreset methods.
The paper tackles the problem of finding sublinear-time quantum algorithms for k-clustering in ℝ^d by developing quantum algorithms that construct coresets with Õ(√nk d^{3/2}) query complexity, reducing input size to poly(kε^{-1}d) and enabling a quadratic speedup for approximation algorithms, complemented by a nearly matching lower bound of Ω(√nk) queries.
$k$-Clustering in $\mathbb{R}^d$ (e.g., $k$-median and $k$-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality $n$, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for $k$-clustering in $\mathbb{R}^d$ with $\tilde{O}(\sqrt{nk}d^{3/2})$ query complexity. Our coreset reduces the input size from $n$ to $\mathrm{poly}(kε^{-1}d)$, so that existing $α$-approximation algorithms for clustering can run on top of it and yield $(1 + ε)α$-approximation. This eventually yields a quadratic speedup for various $k$-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make $Ω(\sqrt{nk})$ queries in order to achieve even $O(1)$-approximation for $k$-clustering.