# Princeton Discrete Math Seminar

## Title:

Quantum Computing

## Speaker:

- Peter Shor
- AT&T Labs

## Place:

- Fine Hall 214
- Princeton University

## Time:

- 3:00 pm - PLEASE NOTE CHANGE OF TIME AND PLACE -
- Thursday February 20, 1997

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. 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 explain quantum computing, and give
an algorithm for prime factorization on a quantum computer that
takes a number of steps which is polynomial in the number of digits
of the integer to be factored. This problem is generally considered
hard on a classical computer. 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. We briefly discuss quantum error-correcting codes, which
to some extent can protect quantum states from decoherence and other
forms of error.

Document last modified on February 14, 19997