Quantum Adiabatic Algorithm for K-Means Clustering


(T) Niels Bohr believed “that anyone who thinks they can contemplate quantum mechanics without getting dizzy doesn’t understand it” while Albert Einstein couldn’t accept quantum mechanics because as he said, “I like to think the moon is there, even if I am not looking at it.”

Hilbert spaces provide the mathematical foundation of quantum mechanics. In quantum computing, qubits can be manipulated as vector spaces to perform linear algebra operations.

Machine learning algorithms require training of large data sets that are represented in linear equations of vectors and matrices. Processing machine learning data requires vectors and tensor products in high dimensional spaces.

Therefore, designing machine learning algorithms to run on quantum computers becomes a no-brainer.

And, this is what Professor Seth Lloyd from MIT is proposing: leveraging emerging quantum computing principles and architectures for running machine learning algorithms.

According to Professor Lloyd, “a CD that holds about 10 billion bits can be turned into a quantum state with a single photon”. And, “we could map the whole Universe — all of the information that has existed since the Big Bang — onto 300 qubits”.

Following is a quick summary from Professor Lloyd about the benefits of quantum processing for machine learning, and a recent talk that he gave:

“In machine learning, information processors perform tasks of sorting, assembling, assimilating, and classifying information. In supervised learning, the machine infers a function from a set of training examples. In unsupervised learning, the machine tries to find hidden structure in unlabeled data. Recent studies and applications focus in particular on the problem of large-scale machine learning – big data – where the training set and/or the number of features is large. Various results on quantum machine learning investigate the use of quantum information processors to perform machine learning tasks, including pattern matching, probably approximately correct learning, feedback learning for quantum measurement, binary classifiers, and quantum support vector machines.

…Quantum machine learning can provide exponential speed-ups over classical computers for a variety of learning tasks. The intuition is straightforward…First, classical data expressed in the form of N-dimensional complex vectors can be mapped onto quantum states over log2 N qubits: when the data is stored in a quantum random access memory (qRAM), this mapping takes O(log2 N) steps. Once it is in quantum form, the data can be post-processed by various quantum algorithms (quantum Fourier transforms, matrix inversion, etc.), which take time O(poly(logN)). Estimating distances and inner products between post-processed vectors in N-dimensional vector spaces then takes time O(log N) on a quantum computer. By contrast…sampling and estimating distances and inner products between post-processed vectors on a classical computer is apparently exponentially hard. Quantum machine learning provides an exponential speed-ups over all known classical algorithms for problems involving evaluating distances and inner products between large vectors.

…We show that the problem of assigning N-dimensional vectors to one of several clusters of M states takes time O(log(MN)) on a quantum computer, compared with time O(poly(MN)) for the best known classical algorithm. That is, quantum machine learning can provide an exponential speed-up for problems involving large numbers of vectors as well (“big quantum data”). We present a quantum version of Lloyd’s algorithm for performing k-means clustering: using a novel version of the quantum adiabatic algorithm one can classify M vectors into k clusters in time O(k log kM N).”


N.P. Landsman, 2006 Lecture Notes on Hilbert Spaces and Quantum Mechanics, Radboud University Nijmegen
Seth Lloyd, Masoud Mohseni, Patrick Rebentrost, Quantum algorithms for supervised and unsupervised machine learning, MIT and Google Research
Professor Seth Lloyd’s page at MIT

Note: The picture above is an illuminated fountain at Lincoln Center in New York.

Copyright © 2005-2014 by Serge-Paul Carrasco. All rights reserved.
Contact Us: asvinsider at gmail dot com.