Monday, June 17
Mudd Hall Auditorium
Chair: Peter M. Winkler, AT&T Research
A digital computer is generally considered an efficient universal computing device; that is, it is believed able to simulate any physical computing device with at most a polynomial increase in computation time. This may not be true when quantum mechanics is taken into consideration. Quantum computers are hypothetical machines which use the quantum mechanical properties of interference and superposition of states. Although no quantum computers have yet been built, there are proposals for constructing such computers that may be feasible. Efficient algorithms exist on quantum computers for the two problems of factoring integers and finding discrete logarithms, problems which are generally thought to be hard on classical computers and which have been used as the basis of several cryptosystems.