Research map / Learning theory and algorithms / Clustering
Near-Optimal Quantum Coreset Construction Algorithms for Clustering
Yecheng Xue, Xiaoyu Chen, Tongyang Li, Shaofeng H.-C. Jiang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Quantum LSH-based approximate nearest neighbor search used in the bicriteria step instead of exact nearest-neighbor computation | k-clustering coreset construction · k-median/k-means coreset | query complexity | Improved |
| Quantum multidimensional approximate summation / counting used to compute per-cluster costs simultaneously instead of classical O(nk) per-point distance sums | coreset construction · k-clustering in R^d | query complexity | Improved |
| Adding an approximate-counting trick that estimates large parts first and leaves small parts for later iterations | multidimensional quantum counting · partition counting | query complexity | No clear effect |
Closest papers by meaning
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.91)
- Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.88)
- A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering (ICML 2025 · similarity 0.87)
- Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing (CVPR 2024 · similarity 0.86)
- Quantum (Inspired) $D^2$-sampling with Applications (ICLR 2025 · similarity 0.85)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
