mlsanityData to 7 Oct 2026

Near-Optimal Quantum Coreset Construction Algorithms for Clustering

arXiv 2306.02826 ↗First posted 5 Jun 2023quant-ph cs.AI cs.DScited by 6

Not on the map. Why?

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.

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

Builds on

23 of 67 references.

References · 23

  1. 2018Supervised learning with quantum enhanced feature spacescited by 654
  2. 2018Fair Clustering Through Fairletscited by 176
  3. 2018q-means: A quantum algorithm for unsupervised machine learningcited by 55
  4. 2017Machine learning & artificial intelligence in the quantum domaincited by 40
  5. 2021A New Coreset Framework for Clusteringcited by 38
  6. 2019Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learningcited by 37
  7. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
  8. 2016Quantum Perceptron Modelscited by 27
  9. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  10. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  11. 2019Sublinear quantum algorithms for training linear and kernel-based classifierscited by 19
  12. 2022The Power of Uniform Sampling for Coresetscited by 18
11 more
  1. 2018Near-Linear Time Approximation Schemes for Clustering in Doubling Metricscited by 14
  2. 2020Coresets for Clustering in Excluded-minor Graphs and Beyondcited by 14
  3. 2020Fully-Dynamic Coresetscited by 9
  4. 2019Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solvingcited by 8
  5. 2018Quantum classification of the MNIST dataset with Slow Feature Analysiscited by 5
  6. 2017Clustering High Dimensional Dynamic Data Streamscited by 4
  7. 2020Sublinear classical and quantum algorithms for general matrix gamescited by 4
  8. 2022On the Fixed-Parameter Tractability of Capacitated Clusteringcited by 4
  9. 2022Quantum Clustering with k-Means: a Hybrid Approachcited by 3
  10. 2022Polylogarithmic Sketches for Clusteringcited by 2
  11. 2022Preparing Many Copies of a Quantum State in the Black-Box Modelcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 0; 2025: 4; 2026: 1.

6 papers.

  1. 2025A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advancescited by 28
  2. 2023Coreset selection can accelerate quantum machine learning models with provable generalizationcited by 4
  3. 2025Provably faster randomized and quantum algorithms for k-means clustering via uniform samplingcited by 2
  4. 2025qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devicescited by 1
  5. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
  6. 2025SubZeroCore: A Submodular Approach with Zero Training for Coreset Selectioncited by 0