Quantum annealing for combinatorial clustering
From MaRDI portal
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.
Recommendations
- Biclustering with a quantum annealer
- A quantum annealing approach to biclustering
- Solving larger maximum clique problems using parallel quantum annealing
- Clustering by quantum annealing on the three-level quantum elements qutrits
- Quantum annealing and related optimization methods
- Quantum annealing of hard problems
- Cluster algorithms for anisotropic quantum spin models.
- A quantum evolutionary algorithm for data clustering
- scientific article; zbMATH DE number 5824031
- A hybrid classical-quantum clustering algorithm based on quantum walks
Cites work
- A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version.
- Algorithm AS 136: A K-Means Clustering Algorithm
- Beitrag zur Theorie des Ferromagnetismus
- Efficient algorithms for divisive hierarchical clustering with the diameter criterion
- Hierarchical clustering schemes
- scientific article; zbMATH DE number 6381735 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Optimization by simulated annealing
- Optimization using quantum mechanics: quantum annealing through adiabatic evolution
- Proceedings of the 1st SIAM international conference on data mining. Chicago, IL, USA, April 5--7, 2001
- Scikit-learn: machine learning in Python
- The elements of statistical learning. Data mining, inference, and prediction
- The Euclidean traveling salesman problem is NP-complete
- Very fast simulated re-annealing
Cited in
(13)- Research and application on a novel clustering algorithm of quantum optimization in server load balancing
- Biclustering with a quantum annealer
- A quantum annealing approach to biclustering
- Clustering by quantum annealing on the three-level quantum elements qutrits
- Data clustering with quantum mechanics
- Emulation of high-performance correlation-based quantum clustering algorithm for two-dimensional data on FPGA
- Balanced \(k\)-means clustering on an adiabatic quantum computer
- Spiking neural network dynamic system modeling for computation of quantum annealing and its convergence analysis
- scientific article; zbMATH DE number 5320186 (Why is no real title available?)
- Applications and computational advances for solving the QUBO model
- Data clustering based on Langevin annealing with a self-consistent potential
- Adiabatic quantum algorithm for multijet clustering in high energy physics
- Quantum state clustering algorithm based on variational quantum circuit
This page was built for publication: Quantum annealing for combinatorial clustering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1617211)
