I think there's a few people (t'Hooft if I remember correctly?) that believe a quantum computer will never be able to experimentally demonstrate this speed-up because some aspect of quantum mechanics is incomplete/incorrect.
Edit: Here's the thread I was thinking of where t'Hooft and Shor discuss this http://physics.stackexchange.com/questions/34217/why-do-peop...
http://rjlipton.wordpress.com/2013/04/27/sex-lies-and-quantu...
Yes, 't Hooft and others, including Leonid Levin and Oded Goldreich, believe that quantum computers won't function because of quantum mechanics breaking down. See, e.g.:
I.e. isn't quantum superposition just a form of parallelization? if the quantum step in Shor's algorithm is replaced with a classical step executed in parallel in many cpus, then the speed up would be of the same order of magnitude as when using a quantum step.
http://en.wikipedia.org/wiki/Shor's_algorithm#Finding_the_pe...
Shor's algorithm is still very theoretical though, we need to actually build a quantum computer to run it first.
The quantum search algorithm is very interesting. However, most people in the field would, I think, agree that a non-oracle separation between quantum and classical would be vastly more interesting. Oracle results feel a little too close to cheating.
There is, incidentally, a nice paper showing that for computing total Boolean functions the quantum oracle model can be no more than polynomially faster than a classical model. This means there can be no exponential speedup for such functions, which is a real pity.
ex.: "Man bites dog" doesn't mean "all of mankind bit a dog", it means "this man bit a dog".
P.S. why did you go with "man bites dog"?
But it's pretty easy to quickly read the headline and interpret it as "the performance of ideal quantum computers is no better than the performance of ordinary PCs."
> Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases.
I'm not sure about this part either. Some smart CS guys apparently think that quantum computing isn't even possible. Leonid Levin (yes, of the Cook-Levin theorem seems to be one of them: http://www.cs.bu.edu/fac/lnd/expo/qc.htm.
Assuming the correctness of quantum mechanics, a quantum computer WILL be faster than classical computers for specific classes of problems, exponentially faster in some cases. This has been mathematically proven. (EDIT: No it hasn't apparently. See Michael Nielsen's response below.)