Simon's algorithm
A quantum algorithm that finds a hidden XOR period in a function exponentially faster than any classical method.
The problem looks contrived: a function satisfies f(x) = f(x ⊕ s) for some secret s; find s. Classically you need around 2n/2 queries before a collision turns up. Daniel Simon showed in 1994 that a quantum computer manages it with a number of queries linear in n. It was the first exponential separation between quantum and classical for a well-defined problem, and Peter Shor has said it was Simon's paper that sent him off to attack factoring.
For twenty years the algorithm was mostly a historical footnote. Then it turned out that many Even–Mansour constructions and MAC modes contain exactly that kind of XOR period, making it the workhorse of quantum cryptanalysis against symmetric schemes.