# q-means: A quantum algorithm for unsupervised machine learning

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2018.

## Built on by (most cited first, 30 of 55)

- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Theory for Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.08566/) (2022)
- [Quantum Federated Learning with Quantum Data](https://mlsanity.com/paper/2106.00005/) (2021)
- [Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.09974/) (2022)
- [Quantum Vision Transformers](https://mlsanity.com/paper/2209.08167/) (2022)
- [Automatic design of quantum feature maps](https://mlsanity.com/paper/2105.12626/) (2021)
- [Tensor networks for interpretable and efficient quantum-inspired machine learning](https://mlsanity.com/paper/2311.11258/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [The role of entanglement for enhancing the efficiency of quantum kernels towards classification](https://mlsanity.com/paper/2209.05142/) (2022)
- [Optimizing Quantum Variational Circuits with Deep Reinforcement Learning](https://mlsanity.com/paper/2109.03188/) (2021)
- [A Leap among Quantum Computing and Quantum Neural Networks: A Survey](https://mlsanity.com/paper/2107.03313/) (2021)
- [Quantum Machine Learning for Finance](https://mlsanity.com/paper/2109.04298/) (2021)
- [Study of Feature Importance for Quantum Machine Learning Models](https://mlsanity.com/paper/2202.11204/) (2022)
- [QuACK: Accelerating Gradient-Based Quantum Optimization with Koopman Operator Learning](https://mlsanity.com/paper/2211.01365/) (2022)
- [Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms](https://mlsanity.com/paper/2203.03604/) (2022)
- [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)
- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [Quantum Visual Fields with Neural Amplitude Encoding](https://mlsanity.com/paper/2508.10900/) (2025)
- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [Application of quantum-inspired generative models to small molecular datasets](https://mlsanity.com/paper/2304.10867/) (2023)
- [Quantum Data Center: Perspectives](https://mlsanity.com/paper/2309.06641/) (2023)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Quantum algorithms for SVD-based data representation and analysis](https://mlsanity.com/paper/2104.08987/) (2021)
- [Quantum Clustering with k-Means: a Hybrid Approach](https://mlsanity.com/paper/2212.06691/) (2022)
- [Multi-Armed Bandits and Quantum Channel Oracles](https://mlsanity.com/paper/2301.08544/) (2023)
- [A Novel Image Classification Framework Based on Variational Quantum Algorithms](https://mlsanity.com/paper/2312.07932/) (2023)
- [Quantum Artificial Intelligence: A Brief Survey](https://mlsanity.com/paper/2408.10726/) (2024)
- [Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems](https://mlsanity.com/paper/2502.11173/) (2025)
- [QFCNN: Quantum Fourier Convolutional Neural Network](https://mlsanity.com/paper/2106.10421/) (2021)

## Abstract (arXiv)

Quantum machine learning is one of the most promising applications of a full-scale quantum computer. Over the past few years, many quantum machine learning algorithms have been proposed that can potentially offer considerable speedups over the corresponding classical algorithms. In this paper, we introduce q-means, a new quantum algorithm for clustering which is a canonical problem in unsupervised machine learning. The q-means algorithm has convergence and precision guarantees similar to k-means, and it outputs with high probability a good approximation of the k cluster centroids like the classical algorithm. Given a dataset of N d-dimensional vectors vi (seen as a matrix V ∈ ℝN × d) stored in QRAM, the running time of q-means is widetildeOleft( k d fracηδ2kappa(V)(μ(V) + k fracηδ) + k2 fracη1.5δ2 kappa(V)μ(V) right) per iteration, where kappa(V) is the condition number, μ(V) is a parameter that appears in quantum linear algebra procedures and η = maxi ||vi||2. For a natural notion of well-clusterable datasets, the running time becomes widetildeOleft( k2 d fracη2.5δ3 + k2.5 fracη2δ3 right) per iteration, which is linear in the number of features d, and polynomial in the rank k, the maximum square norm η and the error parameter δ. Both running times are only polylogarithmic in the number of datapoints N. Our algorithm provides substantial savings compared to the classical k-means algorithm that runs in time O(kdN) per iteration, particularly for the case of large datasets.