** Next:** Quantum Computing
** Up:** Prominent Quantum Algorithms
** Previous:** Shor's Algorithm:
** Contents**

In 1996 L. K. Grover published his paper *A Fast Quantum
Mechanical Algorithm for Database Search* providing a
*O*()
time algorithm for finding a single marked element in an unsorted
database of *N* elements [10]; the best possible
classical algorithm requires (*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.

** Next:** Quantum Computing
** Up:** Prominent Quantum Algorithms
** Previous:** Shor's Algorithm:
** Contents**
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository