Grover's Algorithm Explained Step by Step
The search problem
Suppose you must find one correct answer among N possibilities and the only way to check a candidate is to try it, as with guessing a secret key. A classical computer needs about N tries on average, or half that. Grover's algorithm needs on the order of the square root of N checks.
How amplitude amplification works
- Start with all candidates in an even superposition, each with the same small amplitude.
- Apply an "oracle" that flips the sign of the amplitude of the correct answer. This alone does not change what you would measure.
- Apply a step that reflects all amplitudes about their average. Because the correct answer was flipped, this increases its amplitude a little and shrinks the others.
- Repeat. After roughly the square root of N rounds the correct answer dominates, and measurement finds it with high probability.
Repeating too many times overshoots and the probability falls again, so the number of rounds has to be chosen with care. This is an example of quantum algorithms using interference rather than brute force.
Why the speedup is only quadratic
This limit is not a weakness of today's hardware. It is a proven result that no quantum algorithm can do better than a square root speedup for unstructured search. That contrasts with Shor's algorithm, which exploits hidden structure and gets a far larger advantage.
What it means for security
For a symmetric key, a quadratic speedup roughly halves the effective strength measured in bits, which is why guidance favors longer keys. Hash functions are affected in a similar but not identical way. See hash functions and quantum computers for the details. Importantly, the real cost of a Grover attack includes running the oracle, which means a full encryption or hashing circuit, inside an error corrected machine. Grover's search also parallelizes poorly: splitting the work across several quantum computers divides the time by much less than you would hope. Analyses of practical attacks therefore generally conclude that moderately long keys stay safe.
A frequent misconception is that Grover's algorithm lets a quantum computer simply guess passwords instantly. It does not. It still needs many sequential rounds, each of which runs the entire checking circuit, and it only helps when the only available strategy is trial and error.
Where else it applies
Grover's idea generalizes into amplitude amplification, a building block inside other algorithms. It could speed up certain search or optimization subroutines, but overhead matters, and an asymptotic square root gain can disappear on real hardware if each step is very slow or expensive.
What is still unknown
Whether Grover style speedups will pay off in practical applications, beyond security estimates, depends on the speed and cost of future error corrected machines. For the crypto angle, see post-quantum cryptography and crypto.
Frequently asked questions
What does Grover's algorithm do?
It searches an unstructured set of N possibilities for a marked item in about the square root of N steps.
Does Grover's algorithm break AES?
No. It reduces the effective strength of a symmetric key by about half in bits, which longer keys compensate for.
Why can't Grover's algorithm be faster than a square root?
It is a proven limit for unstructured search. Only problems with hidden structure can get larger quantum speedups.
What is an oracle in Grover's algorithm?
It is a circuit that recognizes the correct answer and marks it. For key search, it contains the whole encryption routine.
Is Grover's algorithm more dangerous than Shor's?
No. Shor's algorithm has a much bigger effect on public key cryptography. Grover's effect is modest and manageable.
Can Grover's algorithm be run on today's computers?
Only on tiny problems, and noise limits results. Large searches need error corrected hardware that does not exist yet.
Keep reading
- Hash Functions and Quantum Computers: Are They Safe?
Are hash functions like SHA-256 safe from quantum computers? Learn how Grover's algorithm affects hashing, mining and blockchains in plain English. - Shor's Algorithm Explained Step by Step
How does Shor's algorithm work? A plain English walk through period finding, why it breaks RSA and elliptic curves in theory, and what hardware it would need. - Quantum Algorithms Explained for Beginners
What is a quantum algorithm? Learn how Shor's, Grover's and other quantum algorithms work in plain English, and which ones matter for cryptography and crypto. - Superposition Explained in Plain English
Superposition lets a qubit hold a blend of 0 and 1. Here is what it really means, what it does not mean, and why it matters.
All Quantum computing guides | Back to top | Search the site
Main pages: Quantum computing explained | Quantum and crypto | Companies | Quantum news | Glossary