DIMACS TR: 94-37

Algorithms for Quantum Computation: Discrete Log and Factoring

Author: Peter W. Shor


A computer is generally considered to be a universal computational device; i.e., it is able to simulate any physical computational device with a cost of at most a polynomial factor in the computation time. It is not clear that this is still true if quantum mechanics is taken into account. Several researchers, starting with David Deutch, have developed models for quantum mechanical computers and investigated their computational properties. We show that these computers can factor integers and find discrete logarithms in polynomial time. All known algorithms for these problems take superloly- nomial time on classical computers.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-37.ps
DIMACS Home Page