Grover's Algorithm:

In 1996 L. K. Grover published his paper A Fast Quantum Mechanical Algorithm for Database Search providing a O($\sqrt{{N}}$) time algorithm for finding a single marked element in an unsorted database of N elements [10]; the best possible classical algorithm requires $\Omega$(N) time. This unordered search problem was not the first problem for which a quantum algorithm was shown to be asymptotically faster than any classical algorithm, but it was the first such problem of real utility. Grover's algorithm is optimal to within a constant factor, so the potential speedup of any quantum algorithm for the unordered search problem is moderate: a quadratic factor. While Shor's algorithm may be of more immediate utility, Grover's algorithm seems more interesting in a theoretical sense, as it highlights an area of fundamental superiority in quantum computation.