A Quantum Annealing-Based Approach to Extreme Clustering
This addresses the computational bottleneck in extreme clustering for large-scale data analysis, though it appears incremental as it adapts quantum annealing to an existing problem.
The authors tackled extreme clustering problems with enormous datasets and large numbers of clusters by developing a distributed method using quantum annealing, which produces optimal clustering assignments under separability assumptions and achieves comparable quality to common algorithms while being a full order of magnitude faster.
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.