Research map / Learning theory and algorithms / Clustering
Quantum (Inspired) $D^2$-sampling with Applications
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a QRAM-based quantum algorithm for approximate D^2-sampling yielding a quantum k-means++ in Õ(ζ²k²) time and a quantum approximation scheme for k-means, then dequantizes D^2-sampling via sample-query access to get a classical QI-k-means++.
Problem
Speeding up D^2-sampling, the core step of k-means++ seeding, for the k-means problem, with provable approximation guarantees in both quantum and classical (quantum-inspired) settings.
Approach
Quantize D^2-sampling using swap test, coherent amplitude estimation, median estimation and rejection sampling over QRAM, prove robustness of k-means++ to the resulting (1±ε) sampling errors, and dequantize the same procedure with Tang's sample-query access to obtain a classical O(Nd)+Õ(ζ²k²d) algorithm.
Key results
- Quantum k-means++ runs in Õ(ζ²k²) time and gives O(log k) approximation with probability at least 0.99, and the paper also gives the first quantum approximation scheme for k-means with polylogarithmic dependence on N.
- QI-k-means++ runs in O(Nd)+Õ(ζ²k²d) classical time; on binarized MNIST its cumulative runtime stays nearly constant as k grows while k-means++ scales poorly with N.
- On binarized MNIST (k=2 to 10) QI-k-means++ clustering costs are comparable to k-means++ (e.g., 6.66 vs 6.83 at k=10, scaled by 10^6).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use QI-k-means++ instead of classical k-means++ | Binarized MNIST seeding across k values · Binarized MNIST | cumulative runtime | Mixed |
| Use QI-k-means++ instead of classical k-means++ | IRIS seeding · IRIS | runtime | Hurt |
| Use QI-k-means++ instead of classical k-means++ | QI-k-means++ seeding · Binarized MNIST, k=2–10 | clustering cost: 8.43 vs 8.35; 8.13 vs 8.10; 7.81 vs 7.74; 7.43 vs 7.38; 7.29 vs 7.44; 7.09 vs 7.17; 6.79 vs 7.12; 6.78 vs 6.91; 6.66 vs | Mixed |
| Use QI-k-means++ instead of classical k-means++ | QI-k-means++ seeding · IRIS, k=2–10 | clustering cost: 538.82 vs 773.26; 253.41 vs 227.50; 112.53 vs 115.33; 96.04 vs 93.45; 83.72 vs 83.21; 64.92 vs 60.14; 58.62 vs 57.98; 56 | Mixed |
Surprising findings
- On IRIS (small N, large aspect ratio) the quantum-inspired method is slower, since runtime is dominated by the sampling term with quadratic dependence on k and ζ.
Limitations
- Running time depends quadratically on the aspect ratio ζ, which can be large for datasets with widely separated clusters.
- Theoretical guarantees rely on QRAM / SQ data structures whose setup cost is linear in Nd.
- Experiments are limited to MNIST and IRIS, with no cost/time evaluation on larger datasets in the main text.
Experimental setup
Datasets: binarized MNIST IRIS
Benchmarks: binarized MNIST IRIS
Metrics: k-means clustering cost cumulative runtime
Baselines: k-means++ AFKMC2 K-MC2 RejectionSampling
Builds on: k-means++ noisy k-means++ Tang dequantization (sample-query access) AFK-MC2 / K-MC2 comparison
Closest papers by meaning
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.88)
- Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing (CVPR 2024 · similarity 0.86)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.85)
- Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions (ICML 2024 · similarity 0.85)
- Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm (NeurIPS 2024 · similarity 0.85)
- Gibbs Sampling of Continuous Potentials on a Quantum Computer (ICML 2024 · similarity 0.83)
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.