Linked by Thom Holwerda on Mon 20th Feb 2012 22:53 UTC
Thread beginning with comment 507940
To view parent comment, click here.
To read all comments associated with this story, please click here.
To view parent comment, click here.
To read all comments associated with this story, please click here.
Except all of our currently used public key cryptography algorithms can be broken by a quantum computer. See https://en.wikipedia.org/wiki/Post-quantum_cryptography . It turns out that NP-complete problems seem to be only hard in the worst case and easy in the average case, so no one knows how to use them for cryptography. Grover's algorithm does allow for faster solutions to NP-complete problems, but they remain exponential.
With a sufficiently powerful quantum computer, Shor's algorithm defeats RSA in polynomial time and a generalization of it can solve the discrete logarithm problem (DSA, Diffie–Hellman, ElGamal) in polynomial time.




Member since:
2010-03-11
err... Actually no. Quantum Computers are NP complete for the same problems as digital computers are. So aside from maybe being faster, quantum computers don't have any advantage.