DIMACS TR: 94-37
Algorithms for Quantum Computation: Discrete Log and Factoring
Author: Peter W. Shor
ABSTRACT
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