MIT's Peter Shor explains why he
devised an algorithm for a quantum computer that could unravel our online data
encryption
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?
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 factorise big numbers, I figured a powerful enough quantum computer could break these systems.
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 factorise big numbers, I figured a powerful enough quantum computer could break these systems.
Did you worry about the implications when you
finished "Shor's algorithm" in 1994?
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.
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.
21 is the biggest number a quantum computer has
factorised. When do we worry?
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.
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.
Quantum cryptography can't be broken by
factorisation. Could it one day replace standard cryptosystems?
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 kilometres or so on the fibre-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.
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 kilometres or so on the fibre-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.
How much harder is it to write an algorithm for a
quantum computer?
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.
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.
Why write quantum algorithms when we don't yet
have proper hardware to run them?
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.
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.
Do you think consumer quantum computers will ever
be commonplace?
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 (-273 °C) for a start. But there probably will be ones physicists can access through the internet.
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 (-273 °C) for a start. But there probably will be ones physicists can access through the internet.
This article appeared in print under the headline
"Quantum conundrum"
Profile
Peter Shor is a computer
scientist at the Massachusetts Institute of Technology. His quantum algorithm
could crack the encryptions that protect our data online – but only if a
powerful enough quantum computer is built
.jpg)
.jpg)
No comments:
Post a Comment