Grover's algorithm
Searches an unsorted set in the square root of the number of steps rather than half of them — a quadratic gain, not an exponential one.
Lov Grover published it in 1996. Finding the right entry among a million with no structure to exploit classically takes half a million attempts on average. Grover's algorithm manages it in about a thousand. The method is called amplitude amplification: the correct answer's amplitude is nudged up step by step while the others are pushed down, and after roughly √N iterations it dominates.
The gain is real but modest next to Shor's. The practical consequence for cryptography is that symmetric key lengths are effectively halved — AES-128 retains a margin equivalent to 64 bits, while AES-256 remains adequate. That is why symmetric encryption does not need replacing ahead of quantum computers, unlike asymmetric.