Grover's algorithm

Imagine a phone book that isn't sorted by name at all — just a random pile of N entries — and you want the one entry that matches a name you know. Classically you have no choice but to check entries one by one, and on average you'll look through about half of them, so the work grows with N. Grover's algorithm is a quantum method that finds that marked entry in roughly the square root of N steps instead. For a list of a million, that's about a thousand checks rather than half a million. It needs an 'oracle': a way to recognize the right answer when it sees it, even if it can't directly point to where the answer is.

Here's the honest mechanism, because it's easy to mishear. The algorithm does not 'try all answers at once' and then read off the winner. It starts with all possibilities sharing equal amplitude, then repeats a two-step move — the oracle flips the sign of the marked answer's amplitude, and a second operation reflects all amplitudes about their average. Each round nudges a little more amplitude toward the correct answer and away from the rest, a process called amplitude amplification. After about sqrt(N) rounds the correct outcome has a high probability of being measured. Run too many rounds and the amplitude overshoots and starts shrinking again, so the number of iterations actually matters.