Research map / Learning theory and algorithms / Clustering
Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing
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.
Uses samples from a D-Wave quantum annealer, not just the best one, to compute calibrated posterior probabilities for balanced k-means clustering and to extract ambiguous coresets.
Problem
Clustering with calibrated uncertainty quantification is NP-hard, and existing adiabatic quantum computing (AQC) clustering methods keep only the best measurement from the noisy annealer, discarding information in the other samples.
Approach
Formulate balanced k-means as a QUBO energy-based model, treat the annealer's measurements as Boltzmann samples, and recompute the posterior over feasible solutions from the sampled set to get calibrated probabilities and a greedy coreset of unambiguous points, with little extra compute.
Key results
- On a 3-cluster, 15-point synthetic task, QA produces well-calibrated posterior probabilities matching SIM and exhaustive search (accuracy 56.1% vs exhaustive 56.4%).
- On 20-point, 4-cluster, 4-D synthetic problems, QA reaches accuracy 12.4% and ARI 34.0% versus SIM 32.4% and 59.2%, showing QA degrades at larger sizes.
- On IRIS subsets (3 clusters/15 points), QA achieves adjusted Rand index 76.8%, matching exhaustive search (76.8%) and above k-means (75.5%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the balanced k-means energy formulation with SIM instead of K-means | Balanced k-means clustering · Synthetic, 15 points, 3 clusters, 2 dim | accuracy: 51.3±1.6 -> 56.4±1.6 | Helped |
| Use the balanced k-means energy formulation with SIM instead of K-means | Balanced k-means clustering · Synthetic, 30 points, 3 clusters, 2 dim | accuracy: 37.0±1.5 -> 38.6±1.5 | No clear effect |
| Use the balanced k-means energy formulation with SIM instead of K-means | Balanced k-means clustering · Synthetic, 45 points, 3 clusters, 2 dim | accuracy: 52.8±1.1 -> 50.8±1.6 | Hurt |
| Run QA on the 10-point, 2-cluster task instead of K-means | Balanced k-means clustering · Synthetic, 10 points, 2 clusters, 2 dim | accuracy: 70.1±1.4 -> 74.3±1.4 | Helped |
| Run QA on the 20-point, 4-cluster task instead of SIM | Balanced k-means clustering · Synthetic, 20 points, 4 clusters, 4 dim | accuracy: 32.4±1.5 -> 12.4±1.0 | Hurt |
| Use QA instead of K-means on IRIS subsets | Balanced k-means clustering · IRIS subsets, 3 clusters, 15 points | Adjusted Rand Index: 75.5 -> 76.8 | Helped |
| Use QA instead of SIM on IRIS subsets | Balanced k-means clustering · IRIS subsets, 3 clusters, 15 points | Completeness: 81.7 -> 81.7 | No clear effect |
Surprising findings
- QA shows overconfident posteriors at high sparsification, where single incorrect solutions get posterior probability 1.0 due to insufficient sampling.
- At 45 points, k-means gives higher accuracy than the SIM-based formulation, though the formulation has higher completeness and other clustering metrics.
Limitations
- Problem size is limited by current QUBO and qubit capacity; QA performance drops at 20 points and 4 clusters.
- Lagrange multiplier tuning is performed in simulation because of limited QA compute time.
- Synthetic data assumes identity covariance, and real-data experiments violate the assumptions.
Experimental setup
Datasets: synthetic Gaussian clustering tasks IRIS self-collected images of cars, boats and cars towing boats
Benchmarks: synthetic clustering tasks IRIS
Metrics: accuracy completeness adjusted Rand index Fowlkes-Mallows score calibration sparsification curves
Baselines: K-means (balanced) Simulated annealing (SIM) Exhaustive search
Builds on: balanced k-means Arthur and Date balanced k-means QUBO Adiabatic Quantum Computing for Multi Object Tracking one-hot QUBO encoding
Closest papers by meaning
- Sublinear Time Quantum Sensitivity Sampling (NeurIPS 2026 · similarity 0.86)
- Quantum (Inspired) $D^2$-sampling with Applications (ICLR 2025 · similarity 0.86)
- A Sub-Problem Quantum Alternating Operator Ansatz for Correlation Clustering (ICML 2025 · similarity 0.85)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.84)
- QuCOOP: A Versatile Framework for Solving Composite and Binary-Parametrised Problems on Quantum Annealers (CVPR 2025 · similarity 0.83)
- Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm (NeurIPS 2026 · 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.