Breaking the Internet: Peter Shor's Quantum Algorithm

Wednesday - October 18 2023, 21:50 UTC - 1 year ago

Peter Shor developed an algorithm in the mid-1990s that threatened to break the internet's security protocols. Oded Regev from the New York University has improved Shor's algorithm by incorporating techniques from cryptography, and it requires fewer quantum operations to factor large numbers than earlier algorithms. Quantum computers derive their power from qubits which can exist in both 0 and 1 states at the same time.

Peter Shor didn’t set out to break the internet. But an algorithm he developed in the mid-1990s threatened to do just that. In a landmark paper, Shor showed how a hypothetical computer that exploited the quirks of quantum physics could break large numbers into their prime factors far faster than any ordinary classical machine.

The result had implications far beyond mathematics. At the time, a vital component of internet security called public-key cryptography relied on the assumption that factoring large numbers is so computationally difficult as to be effectively impossible. That assumption still underpins some critical protocols today. Shor’s algorithm showed that it would fail spectacularly in a world with powerful quantum computers.

In the past 30 years, computer scientists have streamlined Shor’s algorithm in preparation for the day that quantum technology matures enough to run it. But a new variant, from the New York University computer scientist Oded Regev, is faster in a fundamentally new sense. It’s the first to improve the relationship between the size of the number being factored and the number of quantum operations required to factor it.

"It’s really remarkable that somebody has apparently been able to improve the complexity of this result many, many years later," said Ashley Montanaro, a quantum computing researcher at the University of Bristol. "This is really exciting." Martin Ekerå, a cryptographer at the Swedish National Communications Security Authority, agreed that Regev’s paper is interesting but cautioned that beating the state of the art in practice will require further optimization. "Shor’s original algorithms are already surprisingly efficient, so it is not trivial to make major improvements," he wrote in an email.

Regev developed his new algorithm by augmenting Shor’s algorithm with techniques from a branch of cryptography dealing with high-dimensional geometry. "I would have thought that any algorithm that worked with this basic outline would be doomed," said Shor, an applied mathematician now at the Massachusetts Institute of Technology. "But I was wrong." .

Finding Factors Quantum computers derive their power from the peculiar way they process information. Classical computers use bits, each of which must always be in one of two states, labeled 0 and 1. Quantum bits, or "qubits," can additionally be in combinations of their 0 and 1 states — a phenomenon called superposition. It’s also possible to coax multiple qubits into a collective superposition state: A two-qubit superposition has four components that can perform different computations simultaneously, and the number of such components grows exponentially as the number of qubits increases. That allows quantum computers to effectively perform exponentially many different computations in parallel.

But there’s a catch: Reading the result of a computation performed in superposition only reveals the answer to the part computed by one random component. To reap the benefits of computing in superposition, you must somehow map the end result onto a simpler state where it’s safe to read the result. That’s not possible in most cases, and it’s the main obstacle to carefully analyzing and improving quantum algorithms.