What is Grover's algorithm?
A quantum algorithm, published by Lov Grover in 1996, that searches unsorted possibilities in about the square root of the usual number of tries.
Finding one right code among a million takes about 500,000 tries on average by guessing. Grover’s algorithm takes about 785 rounds. Each round makes the right answer’s amplitude a little larger using interference.
Against encryption, Grover’s algorithm is a mild threat. It effectively halves the length of a key, so doubling key length restores the margin. AES-256, already widely used, is considered safe.
In the lessonsSee it in a simulation
Related
- InterferenceAmplitudes adding up or cancelling when they combine. Quantum algorithms use it to make wrong answers unlikely.
- AmplitudeThe number a qubit holds for each possible result. Squaring it gives the chance of that result.
- Post-quantum cryptographyEncryption that runs on ordinary computers and is designed to resist attacks by quantum computers.