[gajomi]

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-...

[greeneggs]

"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."

I don't believe this. Maybe your classical intuition is wrong, but that doesn't mean you can't develop a quantum intuition. Quantum theory is just a natural generalization of probability theory (with "list of probabilities adding to one" replaced by "list of amplitudes whose squares add to one"), so particularly for anyone who thinks much about randomized algorithms the intuition is very similar.

[da-bacon]

It's an interesting question: how those who work on quantum algorithms think about quantum algorithms. As someone who worked on quantum algorithms for many years, the interesting intuition that I developed was not what made quantum algorithms tick, but more along the lines of "when is a method likely to NOT yield a quantum speedup." That is I found I could pretty quickly tell when I was doing something that had a nice classical analogy and was therefore doomed to failure. Classic examples where when your intuition about why you might get a speedup involved exploring an exponentially large solution space without some reason that interference could be used to help dig out the interesting parts of the global superposition you created.

An interesting example of how one discovers a quantum algorithm is the story of the NAND tree algorithm (See http://www.scottaaronson.com/blog/?p=207 for a nice explanation.) Quite literally the quantum algorithm was discovered by thinking about interference of particles hoping around, combined with physicists uncanny ability to calculate scattering cross sections. Crazy stuff!