Grover's Search

You have a function f from N inputs to {0, 1}. Exactly one input w satisfies f(w) = 1; every other input gives 0. You want to find w. The only thing you can do is evaluate f, and f is a black box — no structure to exploit, no gradient to follow, no ordering to binary-search. Checking one item tells you about that item and nothing else.

Classically the cost is easy to pin down. With no structure, all you can do is try inputs. You expect to find w after about N/2 evaluations, and to be certain you may need all N. There is no cleverness available: this is a proven lower bound, not a failure of imagination. If the haystack has a million items, you are looking at roughly half a million evaluations.

Grover's algorithm, published in 1996, finds w with high probability in about (π/4)√N evaluations. For a million items that is roughly 785 instead of 500,000. It is a quadratic speed-up, not an exponential one — worth being precise about, because the difference matters enormously in practice and gets blurred in popular accounts.

It is also known to be optimal. Bennett, Bernstein, Brassard and Vazirani proved that no quantum algorithm can search an unstructured space in fewer than Ω(√N) queries, and Grover's achieves that bound up to constants. So this is not a waypoint on the road to something faster: for genuinely unstructured search, √N is the end of the line.