Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing

Adiabatic quantum computing (AQC) is a promising approach for discrete and often NP-hard optimization prob-lems. Current AQCs allow to implement problems of re-search interest, which has sparked the development of quan-tum representations for many computer vision tasks. De-spite requiring multiple measurements from the noisy AQC, current approaches only utilize the best measurement, dis-carding 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 ad-ditional 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.