Your first paragraph is quite right. But the second paragraph is wrong: for (non-oracle) problems quantum computers are merely suspected to be faster in principle than conventional classical computers. It's never been proven.
I guess I'm confused then. I thought that quantum algorithms had been proven to be faster than the best known classical algorithms (for instance, Shor's factorization), assuming the correctness and completeness of the postulates of QM. In other words, the order of the algorithm is derivable from the postulates. Is that not the case?
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.
Shor's algorithm is exponentially faster than the best existing classical algorithm for factoring. But that doesn't mean there's not an exponentially faster classical algorithm which would be comparable in speed to Shor's algorithm. Some noted experts believe this is possible, and even likely. Richard Lipton believes it, and claims that Peter Sarnak does too:
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.:
Aren't algorithms like Shor's essentially faster than others in their respected categories due to parallelization?
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.
Not really, if that was the case, quantum computers really would be faster than classical computers. A qubit is basically a normal bit, with probability a that it's in the 0 state, and b that it's in the 1 state, with a^2 + b^2 = 1. If you do some clever maths, you can get these probabilities to cancel out, and give you something that will collapse to the proper state when read.
That's right. The search result, however, assumes the only way of accessing the database is through a black box oracle. That's why I wrote "non-oracle" in my previous comment. It's called an oracle because the internals of the black box are assumed to be unknown. That assumption is necessary in order to prove that classical computers need ~ N operations. If you know something about the internals of the oracle, then it may well be possible to exploit what you know to search faster.
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.
Comments
Your first paragraph is quite right. But the second paragraph is wrong: for (non-oracle) problems quantum computers are merely suspected to be faster in principle than conventional classical computers. It's never been proven.
I guess I'm confused then. I thought that quantum algorithms had been proven to be faster than the best known classical algorithms (for instance, Shor's factorization), assuming the correctness and completeness of the postulates of QM. In other words, the order of the algorithm is derivable from the postulates. Is that not the case?
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...
Shor's algorithm is exponentially faster than the best existing classical algorithm for factoring. But that doesn't mean there's not an exponentially faster classical algorithm which would be comparable in speed to Shor's algorithm. Some noted experts believe this is possible, and even likely. Richard Lipton believes it, and claims that Peter Sarnak does too:
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.:
http://www.wisdom.weizmann.ac.il/~oded/on-qc.html
http://www.cs.bu.edu/fac/lnd/expo/qc.htm
Aren't algorithms like Shor's essentially faster than others in their respected categories due to parallelization?
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.
Not really, if that was the case, quantum computers really would be faster than classical computers. A qubit is basically a normal bit, with probability a that it's in the 0 state, and b that it's in the 1 state, with a^2 + b^2 = 1. If you do some clever maths, you can get these probabilities to cancel out, and give you something that will collapse to the proper state when read.
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.
What about searching an unsorted database? Quantum can do it in O(N^0.5). Hasn't it been proven that classical computers need O(N)?
That's right. The search result, however, assumes the only way of accessing the database is through a black box oracle. That's why I wrote "non-oracle" in my previous comment. It's called an oracle because the internals of the black box are assumed to be unknown. That assumption is necessary in order to prove that classical computers need ~ N operations. If you know something about the internals of the oracle, then it may well be possible to exploit what you know to search faster.
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.
http://arxiv.org/abs/quant-ph/9802049