Machine Learning using Quantum Algorithms

Disclaimer: I do not know much about quantum computation, but got interested in it only very recently. I'll give you my understanding, take it with a grain of salt.

AFAIU, Grover's algorithm is not really an algorithm of search of unstructured data, like phone book, but rather a quantum algorithm for inverting a function. The way it is related to search is that you have to have a computable function f such that f(x)=1 if 'x' is one of the million 'boxes' and f(x)=0 otherwise. Your goal is to find that one 'x' (assumption being, of course, is that 'f' is not easily inversible).

How would traditional computer solve the problem - by going through all x's and once f(x)=1, you have your x.

The power of quantum computer is that the state of the quantum computer is the quantum superposition of many classic states. As such quantum computer may perform a computation of 'f' at the superposition of many 'x's at one and get a superposition of function results (that can be measured with a certain degree of uncertainty)

The algorithm essentially goes through superpositions narrowing sets of possible candidate x's pretty fast. Algorithm is inherently probabilistic but the point is that you can converge to x that is your correct x with a high degree of certainty in a (relatively) small amount of steps.

If anyone has more qualified explanation to offer I will be happy to stand corrected.

The 'database' is not really a database in the sense that it stores a list of things. Instead the database is like a predicate p(x) where x ranges over some finite set (you can assume that this set is just 0..N). So if p(x) really has to search a database to determine whether x is the one you want, then the algorithm doesn't work. It is assumed that executing p(x) is fast. Classically you'd have to call the predicate on each of 0..N to find the x for which p(x) = 1. In a quantum computer you can start with a superposition of all states 0..N (think probability distribution over 0..N), and by cleverly applying a quantum analog to a predicate p in Grover's algorithm you can change this probability distribution so that the x for which p(x) is true gets more and more likely (i.e. more and more probability mass). This probability mass increases fast enough that on average you need O(sqrt(N)) steps to find the x that satisfies p(x).

I feel compelled to point out (as is done here http://michaelnielsen.org/blog/quantum-computing-for-everyon...) that it is possible that no such explanation exists. My understanding is that most people doing theoretical research in quantum computing don't need to have intuitive explanations for their results, since the calculations work themselves out. This is a depressing but honest observation.

I found quantum mechanics courses very frustrating for exactly this reason, especially in grad school, when the calculations became especially dense and the rationale impenetrable (I have since left physics). Occasionally there would be some little gem of insight into a particular phenomena where the result could be explained in a clear way, but the default approach was to just "do the calculation".

I can't explain exactly how a quantum computer works (because I don't understand it myself) but I will say that the reason the kind of analogy given above might make sense from a quantum mechanical perspective is that the state of the system and the operations that mutate the state have semantics different from classical computers. In particular, the state of the system is given by a bunch of complex numbers, which you can think of as a collection of arrows on the plane. The length and direction that these arrows are pointed in determines the probability for a bit having a particular sign. For example if an arrow is aligned more east-to west the measured classical bit will more likely be a 1, whereas if it is aligned north to south, the bit will tend to be a zero. The tricky part comes when one tries to consider how the state changes in time when subject to some operations. Fundamental particles like electrons or photons are "indistinguishable", which is to say that there are no properties intrinsic to a particular particle that allow one to distinguish it from another such particle of the same type. The result is that the arrows describing our bits (which we can think of as fundamental particles) become coupled, or entangled. Unlike classical operations on bits which one can construct by composing operations of single bits separately, quantum operations mutate the state of the whole system, which affects all the directions of our arrows (and thus the probability for realizing a measured classical state) simultaneously, so long as this entanglement can be maintained. The logic of how these arrows mutate is the complicated part, but this is how the quantum computer achieves its properties. [deleted a long and ultimately unhelpful explanation].

This is certainly not a layman's explanation, but this discussion of Deutsch's algorithm is quite nice http://physics.stackexchange.com/questions/3390/can-anybody-...

Thanks for asking this question so I didn't have to.. this sounds so interesting but its a bit hard to grasp not having a science background in this field

You know, it's funny how ridiculous D-wave sounded when they insinuated they were scaling qubits about as fast as Moore's law, but here they are in 2011 with a 512 qubit chip that clearly works. That's nuts.

It's hard to believe our technology has advanced this far so fast.

Combined with technologies like IBM Watson, at this rate in 10 years we'll have no idea what the fuck our computers are even doing anymore.

To clarify: you express your problem as an Ising model, load the model into the D-Wave One QC and it will solve it for you. The interesting thing is that solving Ising models is a NP-hard problem.

D-Wave's current chip has only 128 qubits and it is somewhat limited. As they scale it up (and they are prepared to do so) you will be able to use their computer to solve larger and larger models that could not be solved with standard silicon in a reasonable amount of time.

Indeed that is why many in quantum computing cringe at some of their PR. A minor nit: D-waves machine is programmable, it's just not (thought to be) universal.

This isn't about RAM or CPU limitations, it's about entirely different genres of algorithms that aren't feasible with classical computers.

I don't buy it. Quantum computing is extremely important, ground breaking even for complexity theory and theoretical computer science in general. Quantum computing is to complexity theory what the real numbers are to number theory.

From a practical point of view though there are only two interesting family of algorithms: Shor's Quantum Fourier transform and Grover's square root speedup for searching an unstructured list (give or take). The former doesn't seem very applicable to machine learning (yet?). The later is AFAI am concerned useless for machine learning: if we really want to speed up searching some unordered structure then I think we will rely on sorting for a very long time to come - the advantage is much more impressive than Grover's square root speedup.

May I remind you that in the past 20 years there hasn't been much progress on "practical quantum algorithms" (that is not to say quantum complexity results). I think until something brand new comes out of the quantum computing community, these quantum claims are great PR but that's where it ends ...

That is not how it works Viscanti, gate-based QCs are still toys and it remains to be proved if they will become useful anytime soon. On the other hand D-Wave's adiabatic chip is very promising but it requires you to fit a "square peg in a round hole" - expressing problems into a format their hardware can handle is tricky.