Balanced k-means clustering on an adiabatic quantum computer

Abstract

Adiabatic quantum computers are a promising platform for efficiently solving challenging optimization problems. Therefore, many are interested in using these computers to train computationally expensive machine learning models. We present a quantum approach to solving the balanced k-means clustering training problem on the D-Wave 2000Q adiabatic quantum computer. In order to do this, we formulate the training problem as a quadratic unconstrained binary optimization (QUBO) problem. Unlike existing classical algorithms, our QUBO formulation targets the global solution to the balanced k-means model. We test our approach on a number of small problems and observe that despite the theoretical benefits of the QUBO formulation, the clustering solution obtained by a modern quantum computer is usually inferior to the solution obtained by the best classical clustering algorithms. Nevertheless, the solutions provided by the quantum computer do exhibit some promising characteristics. We also perform a scalability study to estimate the run time of our approach on large problems using future quantum hardware. As a final proof of concept, we used the quantum approach to cluster random subsets of the Iris benchmark data set.