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

Politics

Don’t Worry, Obama Isn’t Sending U.S. Troops to Fight ISIS

But the next president might. 

The Extraordinary Amicus Brief That Attempts to Explain the Wu-Tang Clan to the Supreme Court Justices

Amazon Is Officially a Gadget Company. Here Are Its Six New Devices.

The Human Need to Find Connections in Everything

It’s the source of creativity and delusions. It can harm us more than it helps us.

How Much Should You Loathe NFL Commissioner Roger Goodell?

Here are the facts.

Altered State

The Plight of the Pre-Legalization Marijuana Offender

What should happen to weed users and dealers busted before the stuff was legal?

Surprise! The Women Hired to Fix the NFL Think the NFL Is Just Great.

You Shouldn’t Spank Anyone but Your Consensual Sex Partner

Moneybox
Sept. 17 2014 5:10 PM The Most Awkward Scenario in Which a Man Can Hold a Door for a Woman
  News & Politics
Altered State
Sept. 17 2014 11:51 PM The Plight of the Pre-Legalization Marijuana Offender What should happen to weed users and dealers busted before the stuff was legal?
  Business
Business Insider
Sept. 17 2014 1:36 PM Nate Silver Versus Princeton Professor: Who Has the Right Models?
  Life
Outward
Sept. 17 2014 6:53 PM LGBTQ Luminaries Honored With MacArthur “Genius” Fellowships
  Double X
The XX Factor
Sept. 17 2014 6:14 PM Today in Gender Gaps: Biking
  Slate Plus
Slate Fare
Sept. 17 2014 9:37 AM Is Slate Too Liberal?  A members-only open thread.
  Arts
Brow Beat
Sept. 17 2014 8:25 PM A New Song and Music Video From Angel Olsen, Indie’s Next Big Thing
  Technology
Future Tense
Sept. 17 2014 9:00 PM Amazon Is Now a Gadget Company
  Health & Science
Medical Examiner
Sept. 17 2014 11:48 PM Spanking Is Great for Sex Which is why it’s grotesque for parenting.
  Sports
Sports Nut
Sept. 17 2014 3:51 PM NFL Jerk Watch: Roger Goodell How much should you loathe the pro football commissioner?