4 ms·

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 cl

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-quantum-computers/ 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.wisdom.weizmann.ac.il/~oded/on-qc.html http://www.cs.bu.edu/fac/lnd/expo/qc.htm http://www.cs.bu.edu/fac/lnd/expo/qc.htm

axilmar 12y ago
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.
- keeperofdakeys 12y ago
  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_period 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.

axilmar 12y ago

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.

keeperofdakeys 12y ago
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_period 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.