# Near-Optimal Quantum Coreset Construction Algorithms for Clustering

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 67 references that are in the map.
- First posted on arXiv 5 Jun 2023.

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

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Machine learning & artificial intelligence in the quantum domain](https://mlsanity.com/paper/1709.02779/) (2017)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Quantum Perceptron Models](https://mlsanity.com/paper/1602.04799/) (2016)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Sublinear quantum algorithms for training linear and kernel-based classifiers](https://mlsanity.com/paper/1904.02276/) (2019)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [Fully-Dynamic Coresets](https://mlsanity.com/paper/2004.14891/) (2020)
- [Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving](https://mlsanity.com/paper/1911.07306/) (2019)
- [Quantum classification of the MNIST dataset with Slow Feature Analysis](https://mlsanity.com/paper/1805.08837/) (2018)
- [Clustering High Dimensional Dynamic Data Streams](https://mlsanity.com/paper/1706.03887/) (2017)
- [Sublinear classical and quantum algorithms for general matrix games](https://mlsanity.com/paper/2012.06519/) (2020)
- [On the Fixed-Parameter Tractability of Capacitated Clustering](https://mlsanity.com/paper/2208.14129/) (2022)
- [Quantum Clustering with k-Means: a Hybrid Approach](https://mlsanity.com/paper/2212.06691/) (2022)
- [Polylogarithmic Sketches for Clustering](https://mlsanity.com/paper/2204.12358/) (2022)
- [Preparing Many Copies of a Quantum State in the Black-Box Model](https://mlsanity.com/paper/2207.11014/) (2022)

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

- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Coreset selection can accelerate quantum machine learning models with provable generalization](https://mlsanity.com/paper/2309.10441/) (2023)
- [Provably faster randomized and quantum algorithms for k-means clustering via uniform sampling](https://mlsanity.com/paper/2504.20982/) (2025)
- [qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices](https://mlsanity.com/paper/2510.22540/) (2025)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [SubZeroCore: A Submodular Approach with Zero Training for Coreset Selection](https://mlsanity.com/paper/2509.21748/) (2025)

## Abstract (arXiv)

k-Clustering in ℝd (e.g., k-median and k-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality n, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for k-clustering in ℝd with tildeO(√nkd3/2) query complexity. Our coreset reduces the input size from n to poly(kε-1d), so that existing α-approximation algorithms for clustering can run on top of it and yield (1 + ε)α-approximation. This eventually yields a quadratic speedup for various k-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make Omega(√nk) queries in order to achieve even O(1)-approximation for k-clustering.