The Quantum Algorithm That Could Break the Internet

Stories from New Scientist.
Nov. 30 2013 7:09 AM

The Quantum Algorithm That Could Break the Internet

When does a quantum computer start to get scary?

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.

Advertisement

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.

TODAY IN SLATE

History

The Self-Made Man

The story of America’s most pliable, pernicious, irrepressible myth.

Rehtaeh Parsons Was the Most Famous Victim in Canada. Now, Journalists Can’t Even Say Her Name.

Mitt Romney May Be Weighing a 2016 Run. That Would Be a Big Mistake.

Amazing Photos From Hong Kong’s Umbrella Revolution

Transparent Is the Fall’s Only Great New Show

The XX Factor

Rehtaeh Parsons Was the Most Famous Victim in Canada

Now, journalists can't even say her name.

Doublex

Lena Dunham, the Book

More shtick than honesty in Not That Kind of Girl.

What a Juicy New Book About Diane Sawyer and Katie Couric Fails to Tell Us About the TV News Business

Does Your Child Have Sluggish Cognitive Tempo? Or Is That Just a Disorder Made Up to Scare You?

  News & Politics
Damned Spot
Sept. 30 2014 9:00 AM Now Stare. Don’t Stop. The perfect political wife’s loving gaze in campaign ads.
  Business
Moneybox
Sept. 29 2014 7:01 PM We May Never Know If Larry Ellison Flew a Fighter Jet Under the Golden Gate Bridge
  Life
Atlas Obscura
Sept. 30 2014 10:10 AM A Lovable Murderer and Heroic Villain: The Story of Australia's Most Iconic Outlaw
  Double X
Doublex
Sept. 29 2014 11:43 PM Lena Dunham, the Book More shtick than honesty in Not That Kind of Girl.
  Slate Plus
Slate Fare
Sept. 29 2014 8:45 AM Slate Isn’t Too Liberal. But… What readers said about the magazine’s bias and balance.
  Arts
Brow Beat
Sept. 29 2014 9:06 PM Paul Thomas Anderson’s Inherent Vice Looks Like a Comic Masterpiece
  Technology
Future Tense
Sept. 30 2014 7:36 AM Almost Humane What sci-fi can teach us about our treatment of prisoners of war.
  Health & Science
Bad Astronomy
Sept. 30 2014 7:30 AM What Lurks Beneath The Methane Lakes of Titan?
  Sports
Sports Nut
Sept. 28 2014 8:30 PM NFL Players Die Young. Or Maybe They Live Long Lives. Why it’s so hard to pin down the effects of football on players’ lives.