News for hackers. Stuff that matters.
Re:Performance of quantum computer no better than ordinary P... by michael_nielsen on Thursday June 19, 2014 @04:47PM (#7918209)
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

Re:Performance of quantum computer no better than ordinary P... by axilmar on Friday June 20, 2014 @05:39AM (#7920066)
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.

Re:Performance of quantum computer no better than ordinary P... by keeperofdakeys on Saturday June 21, 2014 @09:39AM (#7924930)
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.