# AT&T Quantum Computing Seminar

## Title:

Prime Factorization on a Quantum Compute

## Speaker:

- Peter Shor
- AT&T

## Place:

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

## Time:

- 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

**contact:**

- Andre Berthiaume
- email: berthiau@research.att.com
- tel: (908) 582-7911

dimacs-www@dimacs.rutgers.edu
Document last modified on November 15, 1996