For many years the study of quantum computing was primarily an academic curiosity, that changed rapidly in 1994, when Peter Shor published his paper ``Algorithms for quantum computation: Discrete logarithms and factoring.'' The primary result of the paper was a polynomial time algorithm for factoring large integers. [Shor94] It is not known if there is a classical algorithm for factoring large integers efficiently, but the best algorithms published thus far are super-polynomial. [WC98] This algorithm coupled with the prominence of cryptographic systems based on factoring large integers fueled study of quantum computation, both from a algorithmic and a manufacturing point of view.

Shortly after that, in 1996 L. K. Grover published his paper providing
a
*O*() time algorithm for finding a single marked element in
an unsorted database of *n* elements. [Grover96] The best possible
classical algorithm will run in *O*(*n*) time. This search problem was
not the first problem for which a quantum computer was shown to be
better than any possible classical computer, but it was the first
problem of real utility found where a quantum computer outperforms a
classical computer in an asymptotic sense. While Shor's algorithm may
be of more immediate utility, Grover's algorithm seems more
interesting in a theoretical sense, as it identifies substantial
efficiency for a real world problem in quantum computation.