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

The status of quantum computing as a matter of academic curiosity
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
quantum algorithm for factoring large integers
[17]. It is not known if there is a classical
algorithm for factoring large integers efficiently, but the best
algorithms published thus far are exponential
[18]. The presumed difficulty of factoring
large integers is the basis for most modern cryptography. The
importance of cryptography and its potential frailty in the face of
Shor's algorithm argue for earnestly researching the practicality of
constructing a quantum computer; this endeavor is currently ongoing in
multiple corporate, government, and academic research facilities
[12] [8].

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