Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum
  Computing
Jan-Nico Zaech Martin Danelljan Luc Van Gool
Adiabatic quantum computing (AQC) is a promising quantum computing 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 machine learning and 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 and real data.