Peter Shor (AT&T Bell Labs)
A computer is generally considered to be a universal computational device;
that is, it is believed able to simulate any physical computational device
with a cost in computation time of at most a polynomial factor. It is not
clear whether this is still true when quantum mechanics is taken into
consideration. A quantum computer is a hypothetical machine which uses
quantum mechanics to perform computations. We will give algorithms for
prime factorization on a quantum computer that take a number of steps which
is polynomial in the number of digits of the integer to be factored.
This problem are generally considered hard on a classical computer and has
been used as the basis of several proposed cryptosystems. So far, quantum
computers are purely thought experiments; it is not clear whether it will
be possible to build one. This result does show that simulating arbitrary
quantum mecanical systems is at least as hard as factoring.