2023/06/05 by Yecheng Xue, Xue, Yecheng, Xiaoyu Chen +5 · 2 citations
Computer Science · #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2306.02826
openalex publication_date 2023/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
k-Clustering in ℝ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 ℝd with O(√(nk)d3/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.