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
contact: