April 24, 2014

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.