Guillaume Palacios's presentation ( The D-Wave “Quantum Computer” Myths and Realities) at the recent Paris Machine Learning meetup got me thinking that this Quantum Computer might not all PR after all. It turns out that Google Tech Talks just released a video of Seth Lloyd on the subject of Quantum Machine Learning. At around 30 minutes, Seth describes the encoding of information from a CD into a Quantum state in a set up that parallels the single pixel camera.
Here is a recent ArXiv preprint on the subject:
Quantum algorithms for supervised and unsupervised machine learning by Seth Lloyd, Masoud Mohseni, Patrick Rebentrost
Machine-learning tasks frequently involve problems of manipulating and classifying large numbers of vectors in high-dimensional spaces. Classical algorithms for solving such problems typically take time polynomial in the number of vectors and the dimension of the space. Quantum computers are good at manipulating high-dimensional vectors in large tensor product spaces. This paper provides supervised and unsupervised quantum machine learning algorithms for cluster assignment and cluster finding. Quantum machine learning can take time logarithmic in both the number of vectors and their dimension, an exponential speed-up over classical algorithms.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
So, according to Lloyd's abstract, one can do AI with polynomial time complexity. Doesn't that sound too good to be true to you?
ReplyDeleteAccording to this later paper:
http://arxiv.org/abs/1401.2142
the Lloyd algorithm will perform poorly most of the time, and an algorithm that performs decently requires exponential time complexity.