Abstract
k-Clustering in 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 R^d with O(√nkd^3/2) query complexity. Our coreset reduces the input size from n to poly(kε⁻¹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 Ω(√nk) queries in order to achieve even O(1)-approximation for k-clustering.