Re:What could the NSA do with a quantum computer?
by gizmo686 on Friday June 28, 2013 @02:31PM
(#5959591)
Regarding computability yes. Regarding time complexity, it is unproven.
What we do know is that there is a known algorithm to factor number in polynomial time on quantum computers and there is not a known algorithm to do so on classical computers. Assuming that factoring numbers is actually a hard problem on classical computers (unproven, but generally accepted), then quantum computers are more powerful than classical ones.
What we do know is that there is a known algorithm to factor number in polynomial time on quantum computers and there is not a known algorithm to do so on classical computers. Assuming that factoring numbers is actually a hard problem on classical computers (unproven, but generally accepted), then quantum computers are more powerful than classical ones.