Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

HOW TO COMPUTE WITH SCHROEDINGER'S CAT, an Introduction to Quantum Computing.


Speaker: Eleanor Rieffel, XEROX PARC Palo Alto.
Location: 693 Kerr
Start time: Mon, Apr 26 1999, 4:10PM

In the early 1980's, Richard Feynman observed that certain quantum mechanical effects could not be simulated efficiently on a computer. This observation led to speculation that perhaps computation in general could be done more efficiently if it made use of these quantum effects. But building quantum computers, computational machines that used these effects, proved tricky, and as no one was sure how to use them to speed up computation anyway, the field developed slowly.

It wasn't until 1994, when Peter Shor surprised the world by describing a polynomial time quantum algorithm for factoring integers, that the field of quantum computing came into its own. Peter Shor's work prompted a flurry of activity, both among experimentalists trying to build quantum computers and theoreticians trying to find other quantum algorithms.

In this talk I will introduce enough of the basic principles of quantum mechanics to explain where the computational power of quantum computers comes from and why it is difficult to harness. A high level overview of currently known techniques for harnessing this power, including Shor's algorithm, will be given.