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