2001

Quantum Computer Factors “15”

Peter Shor (b. 1959), Isaac Chuang (b. 1968)

Speed is the promise of quantum computers—not just faster computations, but mind-blowingly, seemingly impossibly fast computations.

That’s a problem for anyone who sends encrypted information over the internet, because the public key cryptography algorithms that secure the majority of the internet’s data depend on the difficulty of factoring large numbers. There is no known algorithm for efficiently factoring large numbers on a conventional computer. But in 1994, mathematician Peter Shor devised an algorithm for efficiently factoring large numbers on a quantum computer. This means that an organization with a working quantum computer could decrypt practically every message sent over the internet—provided the organization had a large enough quantum computer.

One way to measure a quantum computer is by the number of qubits it can process at a time. In 2001, a team of scientists at IBM’s Almaden Research Center led by Isaac Chuang successfully factored the number 15, yielding the factors 3 and 5, with a quantum computer that had 7 qubits.

Although factoring the number 15 might not seem like a big deal, the IBM researchers proved that quantum computers aren’t just theoretical—they actually work. Now the race was on to make a quantum computer that was large enough to compute something that could not be computed on a conventional machine.

Since then, quantum computers have gotten steadily bigger, and the factoring algorithms have also improved. In 2012, Shor’s algorithm was used on a 10-qubit machine to factor the number 21. That same year, a team in China factored the number 143 with a 4-qubit computer using an improved algorithm. Astonishingly, two years after the Chinese team published its findings, a group of researchers at Kyoto University pointed out that the Chinese system had also factored the numbers 3,599, 11,663, and 56,153, without the authors even being aware of it!

Cryptographers at the US National Institute of Standards and Technology are now racing to develop “post-quantum” encryption algorithms that aren’t based on factoring and, as a result, won’t be vulnerable to anyone who has a quantum computer.

SEE ALSO The Qubit (1983)

In 2001, a team of scientists used a quantum computer with 7 qubits to factor the number 15, yielding the factors 3 and S. Since then, quantum computers have factored much larger numbers.