# Coreset Clustering on Small Quantum Computers

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2020.

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

- [Systematic Literature Review: Quantum Machine Learning and its applications](https://mlsanity.com/paper/2201.04093/) (2022)
- [Quantum Machine Learning on Near-Term Quantum Devices: Current State of Supervised and Unsupervised Techniques for Real-World Applications](https://mlsanity.com/paper/2307.00908/) (2023)
- [An Invitation to Distributed Quantum Neural Networks](https://mlsanity.com/paper/2211.07056/) (2022)
- [Quantum Machine Learning for Finance](https://mlsanity.com/paper/2109.04298/) (2021)
- [Clustering by Contour coreset and variational quantum eigensolver](https://mlsanity.com/paper/2312.03516/) (2023)
- [Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling](https://mlsanity.com/paper/2504.20982/) (2025)
- [Coreset of Hyperspectral Images on Small Quantum Computer](https://mlsanity.com/paper/2204.04691/) (2022)
- [qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices](https://mlsanity.com/paper/2510.22540/) (2025)
- [Training Quantum Boltzmann Machines with Coresets](https://mlsanity.com/paper/2307.14459/) (2023)
- [PASS: Certified Subset Repair for Classical and Quantum Pairwise Constrained Clustering](https://mlsanity.com/paper/2601.20157/) (2026)

## Abstract (arXiv)

Many quantum algorithms for machine learning require access to classical data in superposition. However, for many natural data sets and algorithms, the overhead required to load the data set in superposition can erase any potential quantum speedup over classical algorithms. Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing to address this issue, relying on coresets to minimize the data loading overhead of quantum algorithms. We investigate using this paradigm to perform k-means clustering on near-term quantum computers, by casting it as a QAOA optimization instance over a small coreset. We compare the performance of this approach to classical k-means clustering both numerically and experimentally on IBM Q hardware. We are able to find data sets where coresets work well relative to random sampling and where QAOA could potentially outperform standard k-means on a coreset. However, finding data sets where both coresets and QAOA work well--which is necessary for a quantum advantage over k-means on the entire data set--appears to be challenging.