[takeoutweight]

This is a VERY common misconception, and is not a good intuition for how quantum computing is different than classical.

A better intuition, in my opinion, is computing with "un-flipped" coins, except with funny complex-valued probabilities of heads vs tails instead of real values between 0.0 and 1.0. Because the probabilities are complex-valued, they interact in ways that can seem a bit counter-intuitive, (it makes sense it is counter-intuitive, because how many quantities do we deal with day-to-day that are described with complex numbers?) These interactions can provide some algorithmic speed up on some nicely structured problems.

It's not always obvious what these problems are, and it doesn't relate to do whether the problem is highly-parallel. My intuition for "quantum-friendly" is if a problem involves some kind of periodicity, or Fourier-like frequency analysis, then perhaps you'll see a quantum speedup. But it's important to remember the coins don't somehow "try every flip possible" to find the answer you're looking for -- if they did that you'd be able to solve NP problems in constant time.

[ssivark]

I agree that the superposition with complex probability amplitudes (fundamental quantum randomness) is different from just statistical randomness of trying every possibility. I fact, this is one of the notions which is being used to verify whether the D-Wave computer (as a black box) is "truly quantum".

1. I don't quite see what periodicity has to do with the speedup. Could you elaborate on that?

2. "...if they did that you'd be able to solve NP problems in constant time." Again, please explain. In QM, the answer you calculate is actually the weighted sum over all possibilities... so the way I see it, it does cover every possible path. That answer might not be useful in telling you which is the shortest single path, but if you were an electron traversing a graph and wanted to optimize your travel, you'd do exactly what the quantum computer says and traverse all paths! The classical notion of "best path" might be trickier to deduce from a quantum computer. Maybe I'm addressing something tangential to what you're saying.

[takeoutweight]

Re 1. Periodicity: The quantum Fourier transform is an operation that reflects information about a quantum state into the the phases of the amplitudes. Quantum phase information is exactly where quantum computing differs from classical probabilistic computing, so it makes sense that this technique might show up in places where quantum computing beats classical. For example: Shor's factorization of integers makes direct use of the quantum Fourier transform. I mention periodicity only as an example of a sort of problem where the Fourier transform might be useful. This is as an alternative intuition to what quantum computers are "good at" to combat the notion that "quantum computing is good for parallel problems."

Re 2. "covering all paths": I don't have a problem interpreting quantum superposition as inhabiting all possible states. However, classical probabilistic computing also can be interpreted this way: an un-flipped coin is both heads and tails until the flipping happens. But probabilistic computing doesn't give us faster-than-classical speedup, therefore it's not just the "existing in all states at once" that buys us the speedup: it's the unique kind of math we can do on these states because our amplitudes are unitary-complex, not positive-real.

You understand this distinction, so I perhaps shouldn't have adopted the tone I did (sorry!). The leap between "superposition involves a complex-valued combination of several states" and "tries all answers at once so is very fast" is a very common leap made in popular science articles and is the kind of misconceptions that I think the "quantum computers are good at parallel" intuition encourages. Just because a quantum state is a superposition doesn't mean we get to, for free, observe and evaluate all those states and pick out the one we like. We can sometimes arrange things in such a way that the quantum phases interact non-classically to leverage the structure of some problems to reveal information that isn't available to classical algorithms.

Periodicity information, via the quantum Fourier transform, is an example of one way to arrange things to extract information that would be more expensive to calculate classically.