[edit]
Near-Optimal Quantum Coreset Construction Algorithms for Clustering
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:38881-38912, 2023.
Abstract
k-Clustering in Rd (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 Rd with ˜O(√nkd3/2) query complexity. Our coreset reduces the input size from n to poly(kϵ−1d), 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.