What is Grover’s algorithm?

Searching an unsorted list of N items takes about N checks on a classical computer, because nothing points to the right entry. Grover’s method uses quantum interference to build up the amplitude of the right answer, and it needs about the square root of N steps.

That is a quadratic speedup. Shor’s algorithm gains far more, because it reduces factoring and discrete logarithms to polynomial work, where the best classical methods need far more.

• A symmetric key of n bits has 2^n possible values, so a brute-force search takes about 2^n guesses on a classical computer.
• Grover’s method reduces that to about 2^(n/2) steps, so a 256-bit key falls to about 128 bits of work.
• Finding the input behind a hash, called a preimage, is the same kind of search, so a 256-bit hash also falls to about 128 bits of work.
• Doubling the key or hash length restores the original margin against this attack.

Grover’s method halves the bits of symmetric keys and hashes, while Shor’s algorithm breaks RSA and elliptic-curve keys outright. The fix for Grover is a longer key, and the fix for Shor is a different kind of cryptography.