Quantum Annealing for Combinatorial Clustering

Abstract

Clustering is a powerful machine learning technique that groups "similar" data points based on their characteristics. Many clustering algorithms work by approximating the minimization of an objective function, namely the sum of within-the-cluster distances between points. The straightforward approach involves examining all the possible assignments of points to each of the clusters. This approach guarantees the solution will be a global minimum, however the number of possible assignments scales quickly with the number of data points and becomes computationally intractable even for very small datasets. In order to circumvent this issue, cost function minima are found using popular local-search based heuristic approaches such as k-means and hierarchical clustering. Due to their greedy nature, such techniques do not guarantee that a global minimum will be found and can lead to sub-optimal clustering assignments. Other classes of global-search based techniques, such as simulated annealing, tabu search, and genetic algorithms may offer better quality results but can be too time consuming to implement. In this work, we describe how quantum annealing can be used to carry out clustering. We map the clustering objective to a quadratic binary optimization (QUBO) problem and discuss two clustering algorithms which are then implemented on commercially-available quantum annealing hardware, as well as on a purely classical solver "qbsolv." The first algorithm assigns N data points to K clusters, and the second one can be used to perform binary clustering in a hierarchical manner. We present our results in the form of benchmarks against well-known k-means clustering and discuss the advantages and disadvantages of the proposed techniques.

References in corpus (3)

• Scikit-learn: Machine Learning in Python
• Quantum Annealing in the Transverse Ising Model
• Quantum Annealing for Dirichlet Process Mixture Models with Applications to Network Clustering

Cited by in corpus (33)

• Quantum Annealing for Industry Applications: Introduction and Review
• Quantum computing for finance
• QUBO Formulations for Training Machine Learning Models
• Quantum Algorithms for Jet Clustering
• Feature Selection on Quantum Computers
• Travel time optimization on multi-AGV routing by reverse annealing
• Training a quantum annealing based restricted Boltzmann machine on cybersecurity data
• Practical Quantum K-Means Clustering: Performance Analysis and Applications in Energy Grid Classification
• Adiabatic Quantum Algorithm for Multijet Clustering in High Energy Physics
• Comparing the effects of Boltzmann machines as associative memory in Generative Adversarial Networks between classical and quantum sampling
• Virtual Screening of Chemical Space based on Quantum Annealing
• Efficient Algorithm for Binary Quadratic Problem by Column Generation and Quantum Annealing
• Preparing ground states of the XXZ model using the quantum annealing with inductively coupled superconducting flux qubits
• Quantum annealing with twisted fields
• Semi-supervised time series classification method for quantum computing
• Quantum annealing approach to Ionic Diffusion in Solid
• Track clustering with a quantum annealer for primary vertex reconstruction at hadron colliders
• Balanced k-Means Clustering on an Adiabatic Quantum Computer
• Clustering Method for Time-Series Images Using Quantum-Inspired Computing Technology
• Individual subject evaluated difficulty of adjustable mazes generated using quantum annealing
• Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
• Online calibration scheme for training restricted Boltzmann machines with quantum annealing
• Quantum-assisted cluster analysis
• Ising-Based Louvain Method: Clustering Large Graphs with Specialized Hardware
• Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
• Entropy Computing, A Paradigm for Optimization in Open Photonic Systems
• Quantum Annealing for Semi-Supervised Learning
• Quantum-annealing-inspired algorithms for multijet clustering
• Minor Embedding for Quantum Annealing with Reinforcement Learning
• Hamiltonian formulations of centroid-based clustering
• Characterization of Locality in Spin States and Forced Moves for Optimizations
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Formulation and evaluation of ocean dynamics problems as optimization problems for quantum annealing machines