# A Quantum Approximation Scheme for k-Means

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 17 references that are in the map.
- First posted on arXiv 16 Aug 2023.

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

- [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)
- [Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions](https://mlsanity.com/paper/1811.00414/) (2018)
- [Streaming PTAS for Constrained k-Means](https://mlsanity.com/paper/1909.07511/) (2019)

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

- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)

## Abstract (arXiv)

We give a quantum approximation scheme (i.e., (1 + varepsilon)-approximation for every varepsilon > 0) for the classical k-means clustering problem in the QRAM model with a running time that has only polylogarithmic dependence on the number of data points. More specifically, given a dataset V with N points in ℝd stored in QRAM data structure, our quantum algorithm runs in time tildeO left( 2^tildeO(frackvarepsilon) η2 dright) and with high probability outputs a set C of k centers such that cost(V, C) ≤ (1+varepsilon) · cost(V, COPT). Here COPT denotes the optimal k-centers, cost(.) denotes the standard k-means cost function (i.e., the sum of the squared distance of points to the closest center), and η is the aspect ratio (i.e., the ratio of maximum distance to minimum distance). This is the first quantum algorithm with a polylogarithmic running time that gives a provable approximation guarantee of (1+varepsilon) for the k-means problem. Also, unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines and has a running time independent of parameters (e.g., condition number) that appear in such procedures.