Grover's Search

An unsorted list of N items takes about N/2 checks classically: there is nothing to exploit, so you look at entries one at a time until one matches. Grover finds the marked item in roughly √N steps instead — for a million items, about a thousand.

It does not do this by being clever about the list. It does it by putting every candidate into superposition at once and then arranging for the wrong answers to interfere destructively while the right one survives.

The oracle flips the sign of the marked amplitude. Press Step once and watch: the marked bar goes negative, and nothing gets taller. Measured at that moment, the state is exactly as useless as it was before — every outcome is still equally likely.

The diffusion step then reflects every amplitude about their mean. Because the marked amplitude sits far below the mean, reflecting it throws it far above. Step through and watch the amber mean line: after the sign flip the mean drops slightly, and the reflection converts that asymmetry into height on exactly one bar.

Keep pressing Step past the optimum and the probability of the marked state goes back down. Grover is a rotation in a two-dimensional plane — one axis is the marked state, the other is everything else — and each iteration turns the state by a fixed angle toward the answer.

Run it too long and you rotate straight past. That is why the iteration count matters, and why the optimal number is ⌊(π/4)√N⌋ = 1 here rather than “as many as you can afford”.