# Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling

arXiv: https://arxiv.org/abs/2504.20982 · HTML: https://mlsanity.com/paper/2504.20982/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 29 Apr 2025.

## Builds on (most cited first, 13 of 13)

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Coreset Clustering on Small Quantum Computers](https://mlsanity.com/paper/2004.14970/) (2020)
- [Convergence rate of stochastic k-means](https://mlsanity.com/paper/1611.05132/) (2016)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Nested Mini-Batch K-Means](https://mlsanity.com/paper/1602.02934/) (2016)
- [Convergence of online k-means](https://mlsanity.com/paper/2202.10640/) (2022)
- [Quantum (Inspired) D2-sampling with Applications](https://mlsanity.com/paper/2405.13351/) (2024)

## Built on by (most cited first, 2 of 2)

- [qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices](https://mlsanity.com/paper/2510.22540/) (2025)
- [PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering](https://mlsanity.com/paper/2601.20157/) (2026)

## Abstract (arXiv)

The k-means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the k-means algorithm is that each iteration requires time linear in the number of data points, which can be expensive in big data applications. This was improved in recent works proposing quantum and quantum-inspired classical algorithms to approximate the k-means algorithm locally, in time depending only logarithmically on the number of data points (along with data dependent parameters) [q-means: A quantum algorithm for unsupervised machine learning, Kerenidis, Landman, Luongo, and Prakash, NeurIPS 2019; Do you know what q-means?, Cornelissen, Doriguello, Luongo, Tang, QTML 2025]. In this work, we describe a simple randomized mini-batch k-means algorithm and a quantum algorithm inspired by the classical algorithm. We demonstrate that the worst case guarantees of these algorithms can significantly improve upon the bounds for algorithms in prior work. Our improvements are due to a careful use of uniform sampling, which preserves certain symmetries of the k-means problem that are not preserved in previous algorithms that use data norm-based sampling.