Algorithms developed so far for quantum computers have typically focused on problems such as breaking encryption keys or searching a list — tasks that normally require speed but not a lot of intelligence. But in a series of papers posted online this month on Arxiv Seth Lloyd of the Massachusetts Institute of Technology in Cambridge and his collaborators have put a quantum twist on AI.

The team developed a quantum version of ‘machine learning’, a type of AI in which programs can learn from previous experience to become progressively better at finding patterns in data. Machine learning is popular in applications ranging from e-mail spam filters to online-shopping suggestions. The team’s invention would take advantage of quantum computations to speed up machine-learning tasks exponentially.

EETimes – Seth Lloyd is proposing q-app (pronounced “quapp”) encodes Google-like queries with q-bits that enable quantum computers to not only perform real-time searches through even the most gigantic databases, but which also insures their absolute privacy, since attempts to eavesdrop on the query by the search engine provider would disturb the delicate q-bit’s superposition of states.

*Programs running on future quantum computers could dramatically speed up complex tasks such as face recognition.*

**Quantum Leap**

At the heart of the scheme is a simpler algorithm that Lloyd and his colleagues developed in 2009 as a way of quickly solving systems of linear equations, each of which is a mathematical statement, such as x + y = 4. Conventional computers produce a solution through tedious number crunching, which becomes prohibitively difficult as the amount of data (and thus the number of equations) grows. A quantum computer can cheat by compressing the information and performing calculations on select features extracted from the data and mapped onto quantum bits, or qubits.

Quantum machine learning takes the results of algebraic manipulations and puts them to good use. Data can be split into groups — a task that is at the core of handwriting- and speech-recognition software — or can be searched for patterns. Massive amounts of information could therefore be manipulated with a relatively small number of qubits.

“We could map the whole Universe — all of the information that has existed since the Big Bang — onto 300 qubits,” Lloyd says.

Such quantum AI techniques could dramatically speed up tasks such as image recognition for comparing photos on the web or for enabling cars to drive themselves — fields in which companies such as Google have invested considerable resources. (One of Lloyd’s collaborators, Masoud Mohseni, is in fact a Google researcher based in Venice, California.)

“It’s really interesting to see that there are new ways to use quantum computers coming up, after focusing mostly on factoring and quantum searches,” says Stefanie Barz at the University of Vienna, who recently demonstrated quantum equation-solving in action. Her team used a simple quantum computer that had two qubits to work out a high-school-level maths problem: a system consisting of two equations. Another group, led by Jian Pan at the University of Science and Technology of China in Hefei, did the same using four qubits.

Putting quantum machine learning into practice will be more difficult. Lloyd estimates that a dozen qubits would be needed for a small-scale demonstration.

Quantum self analysis (Arxiv – 7 page pdf)

Abstract:

The usual way to reveal properties of an unknown quantum state, given many copies of a system in that state, is to perform measurements of different observables and to analyze the measurement results statistically. Here we show that the unknown quantum state can play an active role in its own analysis. In particular, given multiple copies of a quantum system with density matrix R, then it is possible to perform the unitary transformation e^{-i R t}. As a result, one can create quantum coherence among different copies of the system to perform `quantum self analysis,’ revealing the eigenvectors and eigenvalues of the unknown state in time exponentially faster than any existing algorithm.

Quantum support vector machine for big feature and big data classification (Arxiv – 5 page pdf)

Supervised machine learning is the classification of new data based on already classified training examples. In this work, we show that the support vector machine, an optimized linear and non-linear binary classifier, can be implemented on a quantum computer, with exponential speedups in the size of the vectors and the number of training examples. At the core of the algorithm is a non-sparse matrix simulation technique to efficiently perform a principal component analysis and matrix inversion of the training data kernel matrix. We thus provide an example of a quantum big feature and big data algorithm and pave the way for future developments at the intersection of quantum computing and machine learning.

Quantum algorithms for supervised and unsupervised machine learning (Arxiv – 11 pages)

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.

*If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks*