Summer School in Quantum Information Processing - Distinguished Lecture
Series
From Newsletter, September 2001
Peter Shor is a mathematician
at AT&T Labs. His research interests include quantum computing, algorithmic
geometry, and combinatorics. He earned a B.S. in Mathematics at the California
Institute of Technology (Caltech) in 1981, and a Ph.D. in Applied Mathematics at
the Massachusetts Institute of Technology (MIT) in 1985. He was postdoc for a
year at the Mathematical Research Center in Berkeley before starting at AT&T
Bell Laboratories in 1986.
He is recognized worldwide for his work in various
areas of mathematics and computation, most notably for his work in the theory of
quantum computing.
Quantum computation is the study of information
processing in a quantum mechanical framework. Since information is stored in a
physical medium and manipulated by physical processes, it is impossible to
separate any meaningful theory of computing from the laws of physics which
govern computers or other information processors. For most practical purposes,
the classical approximation to the laws of physics has sufficed, and will
probably continue to suffice. However, early last century, scientists realized
that classical physics is wrong and developed a new framework for expressing
physical theory: quantum mechanics. It wasn't until nearly the end of the last
century that scientists started to understand the non-trivial impact the more
precise approximation to the laws of physics, quantum physics, has on the theory
of computation.
A major breakthrough in understanding the power of
quantum computers came in 1994, when Shor showed how, with a quantum computer,
one can factor large numbers using a number of computational steps comparable to
the number of steps needed to multiply two numbers. In other words, if we allow
quantum computational steps, we can factor efficiently. Many public-key
encryption systems in use today require that factoring large numbers is
exponentially harder than multiplying. That is, we need that encoding the
information is roughly as easy as multiplying, but cracking the code is
exponentially harder and thus infeasible. Another widely used class of
public-key encryption systems assumes that finding discrete logarithms in
various mathematical groups is hard, but Shor also came up with an efficient
algorithm for finding discrete logarithms. This algorithm can easily be
generalized in order to crack any of the discrete logarithm based cryptographic
systems. Shor won the 1999 Godel prize for this work. His factoring algorithm
was the topic of his first distinguished lecture.
The discovery of these
algorithms forced scientists to take more seriously the question of whether or
not quantum computers could really be built or if there is some fundamental
reason why large-scale quantum computations cannot be done efficiently. We can
never hope to manipulate quantum systems perfectly, so we need to know if there
is some reasonable way of coping with some degree of errors and inaccuracy. Shor
again provided a major breakthrough on this front, pioneering the field of
fault-tolerant quantum error correction.
Some of his more recent work
includes an elegant new proof (with Preskill) of the security of quantum key
distribution. He has also studied the capacity of various kinds of quantum
channels for transmitting both classical and quantum information; this was the
topic of his second lecture. His pioneering work in quantum computing also
earned him the 1998 Nevalinna Award, the 1998 International Quantum
Communication Award, and a 1999 MacArthur Fellowship. He was also named an
AT&T fellow in 1998.
