Balanced k-Means Clustering on an Adiabatic Quantum Computer

Abstract

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.

References in corpus (11)

• Scikit-learn: Machine Learning in Python
• Quantum Computing in the NISQ era and beyond
• A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm
• Support vector machines on the D-Wave quantum annealer
• Nonnegative/binary matrix factorization with a D-Wave quantum annealer
• QUBO Formulations for Training Machine Learning Models
• Quantum Annealing for Combinatorial Clustering
• Adiabatic Quantum Linear Regression
• Training and Classification using a Restricted Boltzmann Machine on the D-Wave 2000Q
• K-Means Clustering on Noisy Intermediate Scale Quantum Computers
• Quantum-assisted cluster analysis

Cited by in corpus (3)

• Quantum support vector machines for aerodynamic classification
• Discriminating Quantum States with Quantum Machine Learning
• Quantum Discriminator for Binary Classification