# qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 26 Oct 2025.

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

- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Coreset Clustering on Small Quantum Computers](https://mlsanity.com/paper/2004.14970/) (2020)
- [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)
- [Low depth algorithms for quantum amplitude estimation](https://mlsanity.com/paper/2012.03348/) (2020)
- [Quantum Clustering with k-Means: a Hybrid Approach](https://mlsanity.com/paper/2212.06691/) (2022)
- [Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling](https://mlsanity.com/paper/2504.20982/) (2025)
- [Big data applications on small quantum computers](https://mlsanity.com/paper/2402.01529/) (2024)

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

- [PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering](https://mlsanity.com/paper/2601.20157/) (2026)

## Abstract (arXiv)

Clustering on NISQ hardware is constrained by data loading and limited qubits. We present qc-kmeans, a hybrid compressive k-means that summarizes a dataset with a constant-size Fourier-feature sketch and selects centroids by solving small per-group QUBOs with shallow QAOA circuits. The QFF sketch estimator is unbiased with mean-squared error O(varepsilon2) for B,S=Theta(varepsilon-2), and the peak-qubit requirement qpeak=maxD,lceil log2 Brceil + 1 does not scale with the number of samples. A refinement step with elitist retention ensures non-increasing surrogate cost. In Qiskit Aer simulations (depth p=1), the method ran with ≤ 9 qubits on low-dimensional synthetic benchmarks and achieved competitive sum-of-squared errors relative to quantum baselines; runtimes are not directly comparable. On nine real datasets (up to 4.3× 105 points), the pipeline maintained constant peak-qubit usage in simulation. Under IBM noise models, accuracy was similar to the idealized setting. Overall, qc-kmeans offers a NISQ-oriented formulation with shallow, bounded-width circuits and competitive clustering quality in simulation.