Why people believe this
Binary search is fast because it eliminates half the search space each step. Grover's algorithm searches a database quadratically faster than classical — it must work by a similar elimination process.
The correction
Grover's algorithm achieves quadratic speedup through amplitude amplification — not elimination. It starts with equal superposition across all N states, then applies an oracle that flips the phase of the target state, followed by a diffusion operator that reflects all amplitudes around their average. This constructively interferes to increase the target amplitude and destructively interferes to decrease all others. After O(sqrt(N)) iterations the target has near-unit probability. There is no elimination — all states are present throughout.
Try it in the simulator
What to do
Load the Grover preset. Run it and look at the probability bars — |11> has much higher probability than the others. Now clear and place only H gates. Every state has equal probability. Grover does not eliminate wrong answers — it amplifies the right one through interference.
Research notes
Tags