Detail map of New Providence, New Jersey, United States Overview map of New Providence, New Jersey, United States

A: New Providence, New Jersey, United States

Formulation of Shor's Algorithm for Quantum Computers


In 1994 American applied mathematician Peter Shor, working at Bell Labs in Murray Hill, New Jersey, formulated Shor's algorithm, a quantum algorithm for integer factorization. Because Shor's algorithm shows that a quantum computer, or quantum supercomputer algorithm, with a sufficient number of qubits, operating without succumbing to noise or other quantum interference phenomena, could theoretically be used to break public-key cryptography schemes such as the widely used RSA scheme, its formulation in 1994 was a powerful motivator for the design and construction of quantum computers, and for the study of new quantum computer algorithms. It also stimulated research on new cryptosystems secure from quantum computers, collectively called post-quantum cryptography

"In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 × 5, using an NMR implementation of a quantum computer with 7 qubits. However, some doubts have been raised as to whether IBM's experiment was a true demonstration of quantum computation, since no entanglement was observed. Since IBM's implementation, several other groups have implemented Shor's algorithm using photonic qubits, emphasizing that entanglement was observed. In 2012, the factorization of 15 was repeated. Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer" (Wikipedia article on Shor's algorithm, accessed 12-24-2013).

Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26 (1996) 1484–1509, arXiv:quant-ph/9508027v2.

Timeline Themes