AT&T Quantum Computing Seminar


Prime Factorization on a Quantum Compute


Peter Shor


AT&T Laboratories
600 Mountain Avenue
Murray Hill, NJ
Murray Hill Building, Room: 2D-101 - NOTE ROOM CHANGE


2:00 p.m.
Wednesday, November 20, 1996
Please be sure to arrive a few minutes early if you are for outside Murray Hill. Thanks. ABSTRACT:

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. This may no longer be true if quantum mechanics is taken into consideration. In this talk, I explain an algorithm on a quantum computer for factoring large integers into primes that takes order of L cubed steps where L is the number of digits in the integer to be factored. Factorization is generally considered hard on a classical computer, and the best classical algorithms known are nearly exponential in L. So far, quantum computers are purely thought experiments; it is not clear whether it will be possible to build one. One of the main difficulties in building quantum computers is in manipulating coherent quantum states without losing coherence. I also discuss a classification of possible errors in a quantum computer which in later talks in this series will be applicable to quantum error-correcting codes and fault-tolerant computing


Document last modified on November 15, 1996