next up previous contents
Next: Grover's Algorithm: Up: Prominent Quantum Algorithms Previous: Prominent Quantum Algorithms   Contents

Shor's Algorithm:

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 up previous contents
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