Quantum Computing

If computers that you build are quantum / Then spies of all factions will want 'em. / Our codes will all fail, / And they'll read our email, / Till we've crypto that's quantum, / and daunt 'em.

So reads the quantum computing limerick that Peter Shor and his wife co-wrote for a Science News poetry contest. Professor Shor, who is a professor of applied mathematics at MIT, has been studying quantum computing for over two decades.

Prof. Shor’s interest in the field of quantum computing began when he was working for Bell Labs. Intrigued by a presentation given by Umesh Vazirani, Prof. Shor began reading the literature of quantum physics. In particular, Shor was influenced by Simon's problem, a computational problem conceived by computer scientist Dan Simon that can be solved significantly faster on a quantum computer than on a digital computer.

Simon’s problem uses periodicity over the field with two elements, and when Prof. Shor observed this, he realized that if you could use periodicity in the same way over the integers, you could actually solve discrete log. Several months later, Prof. Shor devised the algorithm for factoring and solving discrete log, which is now known as Shor’s algorithm.

Shor’s algorithm enables quantum computers to quickly break through the RSA encryption, which is based on the difficulty of prime factorization. While this is a major threat to security, Prof. Shor explains that cryptographers have time to prepare. He does not expect quantum computers to be able to break RSA encryption for at least 20 more years.

In addition to breaking public-key cryptosystems, quantum computers can perform many computations that traditional computers cannot. One other key benefit of quantum computers is their ability to simulate quantum mechanics. This would have a tremendous impact on the medical field and pharmaceutical industry because it enables quantum computers to model complex chemical reactions.

Prof. Shor also expects that within 20 years, quantum computers will be able to solve high-level combinatorial optimization problems. Quantum computers, therefore, could identify inefficiencies in macro-level systems such as roads, supply chain commerce, and telecommunication infrastructure.

Although there are some problems that quantum computers can solve better than traditional computers, Prof. Shor emphasizes that quantum computers will not replace classical computers. “Quantum computers are not the same as ordinary computers,” he explains. “They’re really two different things. You could ask, ‘What’s the better transportation device, a car or a boat?’ The answer is that it depends on what you want to do with it. The same is true for quantum computers.”

Currently, Prof. Shor’s research focuses on applying quantum information to the study of black holes. His upcoming paper uses quantum information to examine the scrambling time of information in black holes.

Academic Achievements

Peter Shor received his BA in Mathematics from The California Institute of Technology in 1981 and obtained his PhD in Applied Mathematics from MIT in 1985, under the direction of Tom Leighton. After completing a postdoctoral fellowship at the Mathematical Sciences Research Institute in Berkeley, California, he worked at AT&T as a member of the research staff from 1986 to 2003. In 2003, Shor joined the MIT faculty as the Morss Professor of Applied Mathematics, and in 2015, he began serving as the Chair of the Applied Mathematics Committee. Past research interests have included algorithms, combinatorics, probability theory, and computational geometry. His research currently focuses on quantum computing and quantum information theory.

Fact Sheet
CSAIL Quantum Computing Fact Sheet