Quantum Machine Learning

Recently, Google announced their intentions to use quantum algorithms for the search. They implemented Grover's algorithm on the D-Wave chip. Whatever they say about D-Wave, we should admit that quantum computers are going to change the nature of machine learning, it is only a matter of time.

In spite of I had the university course on quantum computing, I am not able to make head or tails of it. (See my recent post about our university education) But, as far as I know, the key idea is a computer can perform exhaustive search in constant time. This means that for quantum algorithms P=NP. For example, the problem of exact MAP inference in an MRF could be efficiently solved via exhaustive search in the space of all possible assignments.

However, quantum computers return probabilistic results, so there remains a work for mathematicians. But it is the work of the different kind. In the field of MRF MAP inference, all the algorithms like loopy BP will be forgotten. Another example: Google's Hartmut Neven developed a quantum version of AdaBoost. So, machine learners, go study quantum mechanics!