Near-Optimal Quantum Coreset Construction Algorithms for Clustering

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^-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.

Tasks

Reproductions