A Quantum Leap in Factoring

In the mid-1990s, Peter Shor, at AT&T Bell Labs and then one of its heirs, AT&T Labs, devised the first algorithms that one day could exploit the intrinsic parallelism of quantum computing. In particular, Shor, now at the Massachusetts Institute of Technology (MIT), showed that quantum techniques could be exponentially faster than any classical computer at finding the factors of a very large number, a task whose difficulty is key to the security of widely used public-key cryptography techniques.

Shor’s breakthrough remains a critical stimulus for the development of quantum computing. “There are a few other algorithmic ideas out there,” said Oded Regev of New York University, but “nothing is as exciting as Shor.” Over the decades, researchers have found ways to significantly reduce the resources required for factoring, but the size needed to crack secure cryptography is still far beyond current quantum hardware’s capability.

Computer scientists often benchmark algorithms based on their asymptotic performance as the size of the problem (for example, the number of bits, n, needed to represent the target to be factored, N) gets very large. Even for the improved implementations, as in Shor’s original algorithm, the number of gates required (a measure of the complexity of the circuit) grows in proportion to n² log n. In August 2023, however, Regev described a new scheme that only requires gates in proportion to n^3/2 log n, whose n^1/2 reduction could be a significant advance for very large n. (The work was posted online and is not yet peer-reviewed.)

Although researchers have proposed quantitative improvements in Shor’s algorithm, “The first time we have an asymptotic improvement is via Regev,” said Vinod Vaikuntanathan of MIT. Still, the new “algorithm should be classified as a theoretical improvement,” Vaikuntanathan stressed. “The practical consequences are still very much to be determined.”

Higher dimensions

A central feature in Shor’s algorithm is calculating the factors of the target number N from the repeat period of a sequence of powers of some chosen constant. (The results are expressed modulo N, that is, as the remainder after dividing by N.) This period is identified using the quantum Fourier transform, which leverages the natural parallelism of quantum mechanics to simultaneously assign the weight of various periodicities to a set of quantum bits, or qubits. A subsequent measurement is highly likely to yield the true period, although the computation may need to be repeated a few times to be sure.

Regev’s innovation is to look for the periodicity in a higher-dimensional space, where points represent the products of different factors, rather than powers of a single one. “A Fourier transform naturally generalizes to higher dimensions,” he said. “In high dimensions, even getting to within some small distance from my starting point I already am able to explore a huge volume.”

The quantum Fourier transform is much more powerful at finding dominant periodicities than its classical counterpart is, although less-prominent frequencies are not saved. The most demanding quantum task in Shor’s factoring algorithm, however, is not the transform itself, but the modular exponentiation that supplies the starting input data for it. Regev’s scheme involves modular multiplication, “taking maybe a few dozen numbers and then just by multiplying them together, without any exponentiation,” he said. “There are so many possible outcomes that you just don’t get if you’re one-dimensional.” These products involve smaller numbers that can be computed more efficiently than the huge powers of a single number, which is the origin of the slower asymptotic dependence of the gate count on n.

Tradeoffs

The new asymptotic efficiency is not free, however. Although the number of quantum gates eventually will be smaller for large-enough n, Regev’s algorithm requires more qubits, of order n^3/2 instead of order n needed in improved versions of Shor’s.

Inspired by the new multi-dimensional approach, however, Vaikuntanathan at MIT and his student Seyoon Ragavan developed a new scheme for modular multiplication, based on the Fibonacci sequence, which they posted in October 2023. This extension was “a pleasant surprise,” Regev said, and “a very clever trick.” By efficiently using reversible operations to re-use hardware, this multiplication scheme can reduce the required number of qubits to order n, the same asymptotic size-dependence as improved versions of Shor’s algorithm.

“People underappreciate the cost of having to do reversible mathematics and how many gates it takes to make these reversible multipliers,” said Ken Brown of Duke University. “If you look at Shor’s algorithm as originally intended, there’s actually very different ways to implement modular exponentiation. There, too, there is a space/time [qubits/gates] tradeoff. You can really compress the total number of parallel operations or time you need, at the cost of more qubits.”

An additional computational burden is the classical circuitry to repeatedly run the algorithm. For Shor’s algorithm, a few repetitions are enough. In contrast, both Regev’s algorithm and the extension require of order n^1/2 repetitions, which is “a concern,” Regev admits. “You don’t get full information after you apply the quantum circuit,” he said. “It gives you some multiple of the periodicity you care about,” so repetitions are needed to determine the correct value.

Practical Consequences

Although the recent work represents the first improvement in the asymptotic performance of factoring algorithms, previous researchers had improved the “constants” in Shor’s algorithm, such as multipliers of the functional dependence on n. “Asymptotics might be misleading,” Regev noted, “in the sense that Shor’s algorithm is extremely optimized in terms of constants.”

“The constants matter,” emailed Martin Ekerå, a cryptographer for the Swedish government, whom Regev described as “the world expert in implementing Shor’s algorithm.” For example, huge 2,048-bit numbers often are used in the Rivest-Shamir-Adleman (RSA) public-key cryptography framework for current applications, but that is not necessarily big enough for the asymptotic advantage to become clear. “By my preliminary analysis, the existing variations of Shor’s algorithm outperform the variation of Regev with the optimizations of Ragavan and Vaikuntanathan for RSA-2048 up to and including RSA-8192,” Ekerå wrote.

Indeed, concerned about potential future vulnerability to quantum factoring, the National Institute of Standards and Technology (NIST) and others advocate alternative “post-quantum” cryptography schemes. As a consequence, “We are not going to see larger keys deployed for RSA in the future,” Ekerå said. “Instead, we are going to see RSA being phased out. What matters to cryptographers is hence which algorithm is the most efficient in practice for breaking RSA with currently commonly used key sizes.”

Uncertain platforms

Assessing and comparing proposed quantum algorithms remains speculative because there is not, so far, a unique strategy for physical implementation. “At this point we don’t have a good understanding of what the model is like. We don’t even know what a qubit would look like,” Regev complained. Adding “questions about fault tolerance and error correction, it gets extremely difficult to really get a sense of what will work best when we one day have quantum computers” that truly deliver on their potential.

Algorithm strategies can trade off the circuit complexity, or depth, with the number of qubits, or space. Regev’s algorithm, for example, uses more qubits as a quantum memory. “Some architectures don’t seem to care about the fact that you have to keep around lots of qubits, just sitting there, doing nothing,” said Vaikuntanathan.

Error correction may also be easier to implement in quantum memories than in computational parts of quantum circuits. In fact, Vaikuntanathan said that he and his student “figured out that Regev is error-correctible, in the sense that even if 10% of the n^0.5 executions are incorrect, I can still extract the output from Regev,” which is “qualitatively more error-tolerant than Shor.”

Future Improvements

Regev’s work is also rather new. “I think there’s more there that we haven’t quite fully explored,” Vaikuntanathan said. “Fundamentally new ideas in this space don’t come around every week, every month—actually, once a year is a big deal. When there is a new idea, there is a great deal of optimism,” although he expects that “It will pass through a hype cycle.”

“I think a few people will likely be inspired to think about further improving these algorithms, and it will be interesting to see how things develop,” Ekerå wrote, “but it is non-trivial to make significant improvements because Shor’s original algorithms are already very efficient.” For his part, Ekerå and Joel Gärtner at KTH Royal Institute of Technology in Stockholm recently extended the new algorithm to compute discrete logarithms, for which Shor developed a quantum algorithm in the same paper as his factoring scheme.

“I hope Regev has found us a new direction for us to all follow, which is we can make the classical side more complex, to then find a new way to speed up the quantum side,” Brown said, “It’s that combination which I think is interesting, which makes this thing work, but also I think points to future ways to make things work. The tough side is that it’s still hard.”

Further Reading

• Regev, O., “An Efficient Quantum Factoring Algorithm,” https://arxiv.org/abs/2308.06572 (2023).
• Ragavan, S., and Vaikuntanathan, V., “Optimizing Space in Regev’s Factoring Algorithm,” https://arxiv.org/abs/2310.00899 (2023).
• Gidney, C., and Ekerå, M., “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433 (2021).