Quantum Clustering Algorithms
Esma Ämeur - Université de Montréal, Canada Gilles Brassard - Université de Montréal, Canada Sébastien Gambs - Université de Montréal, Canada
By the term "quantization", we refer to the process of using quantum mechanics in order to improve a classical algorithm, usually by making it go faster. In this paper, we initiate the idea of quantizing clustering algorithms by using variations on a celebrated quantum algorithm due to Grover. After having introduced this novel approach to unsupervised learning, we illustrate it with a quantized version of three standard algorithms: divisive clustering, k -medians and an algorithm for the construction of a neighbourhood graph. We obtain a significant speedup compared to the classical approach.