Re:What could the NSA do with a quantum computer?
by arjunnarayan on Friday June 28, 2013 @01:53PM
(#5959369)
Quantum computing is not known to allow you to compute NP hard problems in linear (or polynomial) time. Specifically, the relationship between BQP and NP is open, but widely believed to be not equal (just as the general community's priors are biased towards P \neq NP). Here's a hint as to why: http://en.wikipedia.org/wiki/Grover%27s_algorithm#Optimality
If you are interested in what exactly the D-Wave computer is doing, http://www.scottaaronson.com/blog/?p=1400 is a good source.
Re:What could the NSA do with a quantum computer?
by gizmo686 on Friday June 28, 2013 @01:55PM
(#5959385)
Quantum computers cannot solve NP-Complete problems in sub exponential time (we think). If we could measure the quantom state then they would be able to. However there is an exponentially small chance that when we make the measurement we will see the currect answer instead of no result (or simmiliar). Effectively, we need to repeat the computation an exponential amount of times to arrive at the answer.
There is a genneral algorithm that could solve many (all?) NP-Complete problems in the square root of the time it takes classical algorithms, but that is still exponential.
Some people believe the Dwave device shouldn't be labeled as a "Quantum Computer" because the general community typically uses the Quantum Computer label for a device which could compute NP-Complete problems in linear time instead of exponential time, the Dwave device cannot do this.
[1] https://en.wikipedia.org/wiki/Optimization_problem