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 computational machines, quantum computers, that used quantum mechanical effects proved tricky, and
as no one was sure how to use quantum effects to speed up computation, 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. Shor's work prompted a flurry of activity, among both
experimentalists trying to build quantum computers and theoreticians trying to find other quantum algorithms.
In this talk we 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 an overview of Shor's algorithm, will be given.
Eleanor G. Rieffel
Senior Research Scientist, FXPAL
email
Return to Eleanor Rieffel's home page.