# Do you know what q-means?

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 18 Aug 2023.

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

- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions](https://mlsanity.com/paper/1811.00414/) (2018)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension](https://mlsanity.com/paper/1811.04909/) (2018)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Lecture Notes: Selected topics on robust statistical learning theory](https://mlsanity.com/paper/1908.10761/) (2019)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Quantum algorithms for feedforward neural networks](https://mlsanity.com/paper/1812.03089/) (2018)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [An improved quantum-inspired algorithm for linear regression](https://mlsanity.com/paper/2009.07268/) (2020)
- [A Quantum Approximation Scheme for k-Means](https://mlsanity.com/paper/2308.08167/) (2023)

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

- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling](https://mlsanity.com/paper/2504.20982/) (2025)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices](https://mlsanity.com/paper/2510.22540/) (2025)
- [Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model](https://mlsanity.com/paper/2608.02826/) (2026)

## Abstract (arXiv)

Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's algorithm for k-means. This algorithm takes n vectors V=[v1,dots,vn]∈ℝd× n and outputs k centroids c1,dots,ck∈ℝd; these partition the vectors into clusters based on which centroid is closest to a particular vector. We present a classical varepsilon-k-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity tildeObig(frac|V|F2nfrack2dvarepsilon2(k + logn)big), exponentially improving the dependence on the data size n and matching that of the "q-means" quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and Prakash (NeurIPS'19). Moreover, we propose an improved q-means quantum algorithm with time complexity tildeObig(frac|V|F√nfrack3/2dvarepsilon(√k+√d)(√k + logn)big) that quadratically improves the runtime of our classical varepsilon-k-means algorithm in several parameters. Our quantum algorithm does not rely on quantum linear algebra primitives of prior work, but instead only uses QRAM to prepare simple states based on the current iteration's clusters and multivariate quantum amplitude estimation. Finally, we provide classical and quantum query lower bounds, showing that our algorithms are optimal in most parameters.