Grover's Algorithm
A 1996 algorithm that searches an unstructured haystack quadratically faster than brute force. A real quantum speedup, but a modest one.
Grover's algorithm, published in 1996, searches an unstructured haystack quadratically faster than classical brute force: a problem needing a million classical guesses needs only about a thousand quantum steps. The trick is amplitude amplification, rotating the quantum state, query by query, toward the answer.
Quadratic is the operative word. Unlike Shor's exponential speedup, Grover's advantage is modest, and once you account for error-correction overhead and slow quantum clock speeds, the break-even point sits dauntingly far out. Its main practical consequence today is in cryptography: Grover halves the effective strength of symmetric keys, which is why the standard advice is simply to double key lengths, AES-256 instead of AES-128, rather than panic.
A useful calibration: Grover is what a guaranteed quantum speedup looks like when it isn't a revolution.