Peter Shor is known for his internet-breaking algorithm
Christopher Harting
“So, he’s the Beyoncé of this event?” a young woman standing behind me says to a colleague. The three of us are standing, looking at the back of a crowd, whose members are all looking at a bearded man in an orange sweater. Getting a look at him is like trying to see the Mona Lisa – only fleeting glimpses are possible. “His algorithm is the algorithm that will break everything,” the colleague says, as I briefly catch sight of people posing for selfies and getting their conference badges signed.
I’m at the Quantum.Tech World conference in Boston, and Peter Shor is the star attraction. Shor is one of the most influential researchers in the history of quantum computing, and it all comes down to his creation, known as Shor’s algorithm.
In the 1990s, Shor was a researcher at Bell Labs in New Jersey. Quantum computers were a somewhat obscure research topic, barely on his radar, until he attended a seminar by the quantum computing pioneer Umesh Vazirani. There, he heard about a problem that quantum computers could solve better than any conventional computer. The problem was extremely contrived, so Shor wondered whether there was something more practical that quantum computers could be good at, too.
Over the course of about six months, culminating in the spring of 1994, he not only identified such a problem – the factoring of very large numbers – but he also developed a recipe that a quantum computer could follow to solve it. Shor’s algorithm, the one that could “break everything”, was born. It quickly became recognised as an outstanding contribution to the field and gave researchers an urgent reason to actually build quantum computers.
Most modern encryption relies on the mathematical task of factoring very large numbers. As long as computers struggle with this task, our digital data, from emails and medical files to bank transactions, remains safe. But a quantum computer running Shor’s algorithm would be exceptionally good at this. So good, in fact, that a sufficiently powerful quantum computer could use Shor’s algorithm to decrypt our most secure data.
Yet, during a rare quiet moment at the conference in Boston, catching his breath in a makeshift speakers lounge, Shor tells me that he isn’t worried. “We have good methods for post-quantum cryptography, we just have to implement [them],” he said. He pauses, then adds the caveat: “This will be incredibly hard.”
Indeed, there are several well-studied ways of encrypting information that are resistant to his algorithm, and institutions like the National Institute of Standards and Technology (NIST) in the US have already established quantum-proof encryption standards, but adapting them will be both technologically difficult and costly. Large institutions like banks or hospital systems may need years just to audit their communications networks for possible weaknesses, and then an equally long amount of time to update the devices that comprise them and their computer programs.
Shor, wearing his orange sweater, signs a conference badge
Karmela Padavic-Callaghan
And the clock is ticking. The best existing quantum computers are still not reliable and computationally powerful enough to run Shor’s algorithm, but recent years have seen fast progress in terms of both quantum computing hardware and software capabilities. Technology behemoths like Google are now targeting 2029 to complete their migration to post-quantum cryptography, and US President Donald Trump recently signed an executive order requiring that all high-value and high-impact systems within the US government do the same by 2031.
“[Quantum computers] are still toys, but they’ll stop being toys very soon,” says Shor. He tells me that he is impressed with the work researchers have done to make quantum computers bigger, which also increases their computational power. Efforts across academia and industry to improve how quantum computers catch and correct their own errors have been incredible too, says Shor.
He says that people are wrong when they think that anything you can do with a conventional computer, you could do faster with a quantum computer. “I don’t think that quantum computers will help predict the stock market,” he says.
In his view, the set of problems that quantum computing researchers ought to be targeting is fairly narrow. Beyond cryptography, key applications of quantum computing will simulate complex systems from quantum mechanics and molecules of interest to chemistry and biomedicine, in addition to some optimisation problems, says Shor. He is particularly interested in optimisation algorithms, which he says may have been dismissed too quickly by some of his colleagues.
Yet he acknowledges that, so far, developing more truly useful quantum algorithms has proved to be really difficult. Why has no one developed another algorithm as meaningful and powerful as his? He says that he suspects that we are either not smart enough to develop more great quantum algorithms, or that quantum computers simply aren’t useful for all that many tasks.
I can’t help but ask him what he thinks we ought to do to get smarter. We should play with actual quantum computers to see what they can do, and try some weird ideas, he says. “But you have to understand all of quantum mechanics and all of computer sciences, and that’s really a lot to learn.”
Topics:
