Peter Shor, a computer scientist at the Massachusetts Institute of Technology, explains why he devised an algorithm for a quantum computer that could unravel our online data encryption.
Celeste Biever: Internet security relies on the fact that our computers can’t break its cryptosystems. But the quantum algorithm you devised has the potential to do just that. Why create it?
Peter Shor: My motivation was to see what you can do with a quantum computer. An earlier quantum algorithm worked by using periodicity—the tendency of some number sequences to regularly repeat. This is related to factoring, or finding which smaller numbers big numbers are divisible by, so I thought a quantum computer might be able to factor large numbers. As Internet cryptosystems rely on the fact that current computers cannot factor big numbers, I figured a powerful enough quantum computer could break these systems.
CB: Did you worry about the implications when you finished Shor’s algorithm in 1994?
PS: I felt great having discovered something nobody else knew. If I hadn’t done it, someone else would have, eventually. At that time quantum computers were completely hypothetical and I didn’t really think one could be built. Now the only ones that are built are toy ones, so they can’t yet come close to factoring numbers large enough to pose a risk.
CB: Twenty-one is the biggest number a quantum computer has factored. When do we worry?
PS: If you start factoring 10-digit numbers, then it’s going to start getting scary. I think we are pretty safe for five or 10 years, probably more.
CB: Quantum cryptography can’t be broken by factoring. Could it one day replace standard cryptosystems?
PS: For short distances it wouldn’t be too hard to build a quantum key distribution network to encrypt data. Over longer distances, you would need quantum repeaters every 50 kilometers or so on the fiber-optic network, as it’s difficult to maintain a quantum state over long distances. Even if they are cheap by then, it’s a lot of investment.
CB: How much harder is it to write an algorithm for a quantum computer?
PS: Much harder. Quantum computers rely on a form of interference—basically the same phenomenon as light wave interference, in a more mathematical setting. Computational paths to the right answer need to interfere constructively, while those to the wrong answer should interfere destructively. We don’t yet know how to do that in general.
CB: Why write quantum algorithms when we don’t yet have proper hardware to run them?
PS: The more things that you can do with quantum computers, the more important it is to build them. For example, you should be able to use them to better design drugs using quantum effects that predict the molecules’ chemistry. Right now, drug companies use conventional software to simulate those effects, but you might do better if you could use an actual quantum computer.
CB: Do you think consumer quantum computers will ever be commonplace?
PS: I’m not sure they will ever take off. You are not going to have a quantum computer on your desk—they have to be kept at 0.15 Kelvin (minus 273 degrees Celsius), for a start. But there probably will be ones physicists can access through the Internet.
