A ``Killer App'' for Quantum Computing

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($\sqrt{{n}}$) 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.