Near-Optimal Quantum Coreset Construction Algorithms for Clustering
Yecheng Xue Xiaoyu Chen Tongyang Li Shaofeng H. -C. Jiang
$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\epsilon^{-1}d)$, so that existing
$\alpha$-approximation algorithms for clustering can run on top of it and yield
$(1 + \epsilon)\alpha$-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 $\Omega(\sqrt{nk})$ queries in order to achieve even $O(1)$-approximation
for $k$-clustering.