A Quantum Annealing-Based Approach to Extreme Clustering

By Tim Jaschek, Marko Bucyk, & Jaspreet S. Oberoi
Clustering, or grouping, dataset elements based on similarity can be used not only to classify a dataset into a few categories, but also to approximate it by a relatively large number of representative elements. In the latter scenario, referred to as extreme clustering, datasets are enormous and the number of representative clusters is large. We have devised a distributed method that can efficiently solve extreme clustering problems using quantum annealing. We prove that this method yields optimal clustering assignments under a separability assumption, and show that the generated clustering assignments are of comparable quality to those of assignments generated by common clustering algorithms, yet can be obtained a full order of magnitude faster.

Most Recent Papers

Variationally Scheduled Quantum Simulation

By Shunji Matsuura, Samantha Buck, Valentin Senicourt, & Arman Zaribafiyan Eigenstate preparation is ubiquitous in quantum computing, and a standard approach for generating the lowest-energy states of a given system is by employing adiabatic state preparation...

A Feasibility Pump Algorithm Embedded in an Annealing Framework

By Nicolas Pradignac, Maliheh Aramon, & Helmut G. Katzgraber The feasibility pump algorithm is an efficient primal heuristic for finding feasible solutions to mixed-integer programming problems. The algorithm suffers mainly from fast convergence to local optima....