Grover's search
Grover's search algorithm finds a marked item among N choices using about (π/4)√N checks, instead of the N/2 checks a normal computer needs on average. That is a proven quadratic speedup: for a million items, about 785 checks instead of about 500,000. It is not exponential. The "database" must be a test you can run as a quantum circuit, not data sitting in memory. And published estimates argue the gain is unlikely to survive the extra cost of error correction at sizes we could actually build.
| Task | Best classical | Quantum |
|---|---|---|
| Unstructured search, N items | Θ(N) queries (average N/2) | ~(π/4)·√N queries (proven optimal) |
| Brute-force over n-bit inputs | O(2^n) | O(2^(n/2)) |
What problem does it solve?
Grover's algorithm solves unstructured search. You have a test, check(x), and N choices to try. You want an x that passes the test. There is no pattern to help you: no sorting, no hints about getting warmer, no index.
Think of a lock with a million combinations and no clicks to guide you. You just have to try them.
Clear one thing up right away. This is not "searching a database." The test, called the oracle, is a function built into a reversible circuit. Examples are checking a logic puzzle, testing a password guess against a hash, or checking a set of rules. If your data sits in storage, just loading it into a quantum-ready form takes at least N steps. That wipes out the saving before the search even starts.
How would a normal computer do it?
Try choices one by one until one passes. On average that takes N/2 tries. In the worst case it takes N. With no pattern to use, no normal method does better than this.
But normal computers have one big strength: cheap teamwork. Give a thousand processors each a slice of the list, and the wait on the clock drops a thousand times. Remember that when you compare one QPU against real computer centers.
How does Grover's algorithm work?
It does not try all the items at once and pick the winner. If it did, one check would be enough. Grover is proven to need about √N checks. Here is what really happens, with real numbers for our 8-item demo.
An amplitude is a number that sets how likely an answer is. Square it to get the chance. We start with all 8 amplitudes equal to 0.354. That is 1/√8. Check: 0.354 × 0.354 ≈ 0.125, which is 1/8. Each round, called an iteration, has two moves:
- Oracle: flip the sign of the marked item's amplitude. The marked one is now
−0.354. The chance is the amplitude squared, and (−0.354)² is still 0.125. So nothing you can see has changed yet. - Diffusion: flip every amplitude around the average. The new average is (7 × 0.354 − 0.354) ÷ 8 ≈
0.265. Each amplitude moves to "twice the average minus itself." The seven unmarked ones drop to 2 × 0.265 − 0.354 ≈0.177. The marked one jumps to 2 × 0.265 + 0.354 ≈0.884. Square it: 0.884 × 0.884 ≈ 0.78. So the marked item now has a 78% chance after one round.
A second round lifts it to 94.5%. Each round turns the state by the same small angle toward the marked item. That is why about (π/4)√N rounds are needed. It is also why going past the best number of rounds turns you away from the answer again. Think of pushing a child on a swing. Push at the right times and the swing goes higher. Keep pushing too long and you start working against it.
The speedup comes from one simple fact: amplitudes add up in a straight line, while chances are their squares. Nothing more mysterious than that.
What does one iteration cost on real hardware?
Setup plus one Grover round, compiled for three types of device. Each CCX breaks down into about 6 two-qubit gates, and sparsely wired chips add routing on top. Depth (steps in a row) is the enemy of real Grover runs.
What are the honest limitations?
Grover's algorithm is proven correct and proven to be the best possible. Even so, it is hard to turn into a real-world advantage.
- Quadratic, not exponential. It cuts the power in half.
2^128checks become2^64. That is why modern encryption with shared secret keys answers Grover by doubling key lengths, not by panicking. See the RSA-2048 reality check for the contrast with Shor's truly exponential threat. - Every check runs the whole test circuit. The test runs as a reversible circuit inside each of the
√Nrounds. A costly test makes the whole run costly. - No searching stored data. Searching data in memory needs QRAM (quantum memory you can look things up in), which does not exist at scale.
- Error correction may eat the gain. Published estimates, such as Google's Babbush et al. in 2021, looked at this. They concluded that quadratic speedups are unlikely to beat normal hardware once you count the extra cost of error correction and the slower speed of error-corrected qubits. That holds at any problem size we could build.
- Checks happen one after another. The
√Nrounds can't be split across machines, the way normal search easily can.
Where might it truly matter? As a helper step that boosts other quantum algorithms. And for problems with a cheap test and a size in a narrow middle range. See what counts as quantum advantage.
What does this look like on real hardware?
Two- and three-qubit Grover demos work on all the major platforms. The 3-qubit version here has run above 90% success on trapped-ion hardware. That is the honest limit today for clean results.
The problem is depth. Our two-round demo has about 40 gates before transpilation (rewriting into the chip's own gates). Each CCX grows into six or more two-qubit gates on real devices. See native gates and transpilation. Add one qubit and you double the number of choices, but the circuit also gets deeper. Noise builds up with every gate. Past a handful of qubits, the output looks just like random noise unless you use error correction.
Run the demo in the Lab. Then check the compiled depth on real chip layouts on the comparison page.