[codekilla]

I'm not sure it's useful anymore to point to quantum computers and say: 'Hey! You're not getting all your function evaluations back....so they're weak'. I feel this leads to misconceptions about quantum computing as well. You have to remember, the tensor product of N qubits is an exponentially expanding space...and the functions DO get evaluated in that space, the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually. Let's be clear, even with this caveat, the potential of quantum computing is enormous. I've personally read Kalai's papers and in my opinion, his objections boil down to 'it's just too good to be true'....but hey...we'll see :)

[stcredzero]

the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually.

This is an even more succinct way of saying it. This is the key point that people need to know, which separates someone from understanding the real potential of quantum computers from "quantum woo."

Let's be clear, even with this caveat, the potential of quantum computing is enormous.

No question. But to think clearly about it, one has to know this caveat. Likewise, to understand the potential of conventional computers, one needs to actually be able to think about computation within its realistic limits, not treat them as magic boxes.