Balanced k-Means Clustering on an Adiabatic Quantum Computer
This addresses the problem of poor scaling and local optima in classical balanced k-means clustering for large datasets, though it is incremental as it only demonstrates similar performance on small problems.
The authors tackled the balanced k-means clustering training problem using an adiabatic quantum computer, showing that their quantum approach better targets global solutions and achieves better theoretical scalability on large datasets, with clustering performance similar to best classical algorithms on small problems.
Adiabatic quantum computers are a promising platform for approximately solving challenging optimization problems. We present a quantum approach to solving the balanced $k$-means clustering training problem on the D-Wave 2000Q adiabatic quantum computer. Existing classical approaches scale poorly for large datasets and only guarantee a locally optimal solution. We show that our quantum approach better targets the global solution of the training problem, while achieving better theoretic scalability on large datasets. We test our quantum approach on a number of small problems, and observe clustering performance similar to the best classical algorithms.