Grover’s algorithm explained
Grover’s algorithm is a quantum program for searching. Lov Grover published it in 1996 at Bell Labs. With N possibilities, an ordinary computer needs N/2 attempts on average, a quantum computer with Grover only about the square root of N steps. With a million possibilities that is around a thousand instead of half a million.
The task: a needle in a haystack
Imagine a combination lock with seven wheels. There are 10,000,000 possible codes, and only one fits. Without further hints, an ordinary computer has no choice but to try the codes one after another: 5,000,000 attempts on average.
A quantum computer can do this in far fewer steps with Grover’s algorithm. The requirement is a checking rule that can say for each candidate: fits or does not fit.
Try it: does the quantum search find your code? How the quantum search works in three steps
First: all qubits are put into an even superposition with H. Now every possibility is in the state with the same small weight.
Second: the checking rule marks the right possibility by flipping its sign. A measurement would not show anything yet; the probabilities stay the same.
Third: an amplification step reflects all weights about the average. This makes the weight of the marked possibility grow, while all others shrink a little. Marking and amplifying together form one round. After about π/4 times the square root of N rounds, a measurement gives the right answer with very high probability.
How much faster is it?
The advantage is quadratic: N attempts become about the square root of N steps. For our seven-digit combination lock, our simulator calculates with 24 qubits, that is 16,777,216 possibilities, and needs 3,216 rounds instead of 5,000,000 attempts on average.
Grover himself showed that his method is, up to a constant factor, as fast as a quantum search without further hints can be at all. That is a large but not unlimited advantage.
Important: the saved steps count on a real quantum computer. Our simulator recomputes these steps on ordinary hardware so that you can experience them.
What Grover’s algorithm cannot do
More rounds are not better. If you go beyond the right number, the weight of the right answer shrinks again. The number of rounds therefore has to match the size of the search.
In addition, Grover needs a checking rule that the quantum computer can run itself. For an unknown PIN or a password on a server, such a rule is not simply available. Against good encryption with long keys, the quadratic advantage alone is not enough.
Frequently asked questions about Grover’s algorithm
What is Grover’s algorithm, explained simply?
A quantum program for searching. It puts all possibilities into superposition, marks the right one with a checking rule and amplifies it round by round until a measurement gives it with high probability.
Who invented Grover’s algorithm?
Lov K. Grover, then at Bell Labs. He published it in 1996.
How much faster is Grover’s algorithm?
Quadratically faster: instead of about N attempts it needs roughly the square root of N steps. With a million possibilities that is around a thousand steps.
Can Grover’s algorithm crack passwords?
Not just like that. It needs a checking rule that the quantum computer can run itself, and it only speeds up the search quadratically. Long keys therefore remain secure.
Why not simply do more rounds?
Because after the right number of rounds the weight of the correct answer decreases again. Too many rounds make the result worse.
- What is a quantum computer? Explained simply
- What is a qubit?
- Superposition explained simply
- Entanglement explained simply
- Can a quantum computer break encryption?
- Quantum computer simulator
Sources
- Lov K. Grover: A fast quantum mechanical algorithm for database search (Bell Labs, 1996)
- German Federal Government: Quantum computing briefly explained (German)
As of 31 October 2026
Let the quantum search find your code.
Set a test code on the combination lock and watch our simulator search for it. No sign-up.