Hacker News new | ask | show | jobs
by 3PS 2401 days ago
At the moment, quantum computers have only been shown to give exponential speedups over classical computers on problems that can reduced to the special case of the hidden subgroup problem for finite abelian groups [1]. This is only really an issue for public key crypto at the moment (RSA, Diffie-Hellman, and ECC) since secret-key crypto tends to need less structure in the underlying problem. The best you could do to speed up cracking AES with modern quantum algorithms would probably be Grover's algorithm, which only gives a quadratic speedup (an O(N) search becomes O(sqrt(N)) instead). [2]

[1] https://en.wikipedia.org/wiki/Hidden_subgroup_problem

[2] https://en.wikipedia.org/wiki/Grover%27s_algorithm