When physicists first thought up quantum computers in the 1980s, they sounded like a nice theoretical idea, but one probably destined to remain on paper. Then in 1995, 25 years ago this month, applied mathematician Peter Shor published a paper1 that changed that perception.
Shor's paper showed how quantum computers could overcome a crucial problem. The machines would process information as qubits — quantum versions of ordinary bits that can simultaneously be '0' and '1'. But quantum states are notoriously vulnerable to noise, leading to loss of information. His error-correction technique — which detects errors caused by noise — showed how to make quantum information more robust.
Shor, who is now at the Massachusetts Institute of Technology in Cambridge and is also a published poet, had shocked the physics and computer-science worlds the previous year, when he found2 the first potentially useful — but ominous — way to use a hypothetical quantum computer. He'd written an algorithm that would allow a quantum computer to factor integer numbers into prime factors at lightning speed. Most Internet traffic today is secured by encryption techniques based on large prime numbers. Cracking those codes is hard because classical computers are slow at factoring large products.
Quantum computers are now a reality, although they are still too rudimentary to factor numbers of more than two digits. But it is only a matter of time until quantum computers threaten Internet encryption.
Nature caught up with Shor to ask him about the impact of his work — and where Internet security is heading.
View Full Article
No entries found