Quantum Computing

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.