Grover's algorithm

In plain terms

Here is the problem. One marked item hides among N possibilities, with no structure to exploit -- no sorting, no index, nothing. Classically you check items until you hit it: N/2 looks on average, N in the worst case. Surely that is just what search costs.

Grover found that a quantum computer pays square root of N. The procedure is a rhythm: reflect the state about the marked item, reflect about the average, repeat. Each pair of reflections rotates the state a small fixed angle toward the answer; after about root-N steps you measure and find it. Run too long and you rotate PAST the answer -- the algorithm has a punchline but also a timer.

And here is the unusual part: the speedup is provably final. Not just the best known -- the best possible.

In CSD

One of the corpus's algorithm witnesses, with the standard disclaimer stated rather than implied: the algorithms consume the unitary pillar, they do not support it. Their content is circuit semantics -- amplitudes, iteration counts, success probabilities -- not foundations.

What this one demonstrates, beyond expressiveness, is that the formalisation handles genuinely quantitative algorithmics: the rotation-angle bookkeeping and the iteration schedule are exactly the kind of thing that a fragile formal fragment would fumble and this one carries.

Mathematically

Amplitude amplification finds a marked element among N in order root-N oracle queries, versus order N classically. Optimality is a theorem: the BBBV hybrid argument shows no quantum algorithm beats order root-N for unstructured search.

The geometry is two-dimensional: the state stays in the plane spanned by marked and unmarked components, each double reflection rotating it by a fixed angle -- so the query count is a right angle divided by that angle, and overshooting degrades success.

The name

Lov Grover, born 1961 in India, studied at IIT Delhi and Stanford and was at Bell Labs in New Jersey when he published the algorithm in 1996 -- in a paper three pages long, titled as a database search result rather than a physics one.

The optimality half of the story is the strange half: the lower bound (Bennett, Bernstein, Brassard, Vazirani) was proved shortly BEFORE the algorithm existed. The ceiling was known before anyone had built the thing that touches it -- one of the rare cases in algorithms where the achievement and its impossibility-of-more arrived in the wrong order.