# Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 83 references that are in the map.
- First posted on arXiv 18 Oct 2023.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Deep Clustering for Unsupervised Learning of Visual Features](https://mlsanity.com/paper/1807.05520/) (2018)
- [Simple Online and Realtime Tracking](https://mlsanity.com/paper/1602.00763/) (2016)
- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [Joint Discriminative and Generative Learning for Person Re-identification](https://mlsanity.com/paper/1904.07223/) (2019)
- [MotionDiffuser: Controllable Multi-Agent Motion Prediction using Diffusion](https://mlsanity.com/paper/2306.03083/) (2023)
- [Joint Unsupervised Learning of Deep Representations and Image Clusters](https://mlsanity.com/paper/1604.03628/) (2016)
- [Multi-Modal Trajectory Prediction of Surrounding Vehicles with Maneuver based LSTMs](https://mlsanity.com/paper/1805.05499/) (2018)
- [Probabilistic 3D Multi-Modal, Multi-Object Tracking for Autonomous Driving](https://mlsanity.com/paper/2012.13755/) (2020)
- [QUBO Formulations for Training Machine Learning Models](https://mlsanity.com/paper/2008.02369/) (2020)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [Traffic flow optimization using a quantum annealer](https://mlsanity.com/paper/1708.01625/) (2017)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [Adiabatic Quantum Computing for Multi Object Tracking](https://mlsanity.com/paper/2202.08837/) (2022)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [Training and Classification using a Restricted Boltzmann Machine on the D-Wave 2000Q](https://mlsanity.com/paper/2005.03247/) (2020)
- [Learning to rank in person re-identification with metric ensembles](https://mlsanity.com/paper/1503.01543/) (2015)
- [Quantum Motion Segmentation](https://mlsanity.com/paper/2203.13185/) (2022)
- [Quantum Robust Fitting](https://mlsanity.com/paper/2006.06986/) (2020)
- [Control of automated guided vehicles without collision by quantum annealer and digital devices](https://mlsanity.com/paper/1812.01532/) (2018)
- [Quantum Multi-Model Fitting](https://mlsanity.com/paper/2303.15444/) (2023)
- [CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes](https://mlsanity.com/paper/2303.16202/) (2023)
- [Balanced k-Means Clustering on an Adiabatic Quantum Computer](https://mlsanity.com/paper/2008.04419/) (2020)
- [High-quality Thermal Gibbs Sampling with Quantum Annealing Hardware](https://mlsanity.com/paper/2109.01690/) (2021)
- [On the challenges of using D-Wave computers to sample Boltzmann Random Variables](https://mlsanity.com/paper/2111.15295/) (2021)
- [A Probabilistic framework for Quantum Clustering](https://mlsanity.com/paper/1902.05578/) (2019)

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

- [Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms](https://mlsanity.com/paper/2510.07317/) (2025)
- [Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering](https://mlsanity.com/paper/2507.15063/) (2025)
- [Quantum Multiple Rotation Averaging](https://mlsanity.com/paper/2602.10115/) (2026)

## Abstract (arXiv)

Adiabatic quantum computing (AQC) is a promising approach for discrete and often NP-hard optimization problems. Current AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for many computer vision tasks. Despite requiring multiple measurements from the noisy AQC, current approaches only utilize the best measurement, discarding information contained in the remaining ones. In this work, we explore the potential of using this information for probabilistic balanced k-means clustering. Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost. This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.