Quantum algorithms

“This variant of my algorithm was undiscovered for 30 years and came out of the blue, There’s still probably lots of other quantum algorithms to be found.” - Peter Shor

‍

Peter Shor's algorithm of the mid-1990s, which demonstrated how quantum computers could rapidly factor large numbers, posed a major threat to the security of Internet protocols that depend on the difficulty of such factorization. Over the past 30 years, Shor's algorithm has been refined, but recent advances, particularly those of Oded Regev of New York University, have greatly accelerated quantum factorization.

‍

Regev's new algorithm improves the ratio between the size of the number to be factored and the number of quantum operations required, making it the first such improvement in this field. Experts such as Ashley Montanaro and Martin Ekerå consider this breakthrough to be a major step forward, although its practical application will still require further optimization.

‍

Regev's approach combines Shor's algorithm with high-dimensional geometry techniques from lattice-based cryptography, resulting in a faster factorization method. His innovation is to generalize the periodic function from one dimension to multiple dimensions, resulting in a more efficient computational process.

‍

The quantum part of Regev's algorithm now runs with a complexity proportional to 

n^1.5, compared to Shor’s n². Although this requires more qubits (proportional to n^1.5 instead of n), a subsequent refinement by MIT researchers has managed to reduce the memory requirement back to being proportional to n.

‍

This progress highlights that quantum factorization is gaining speed, suggesting that quantum computing researchers must remain vigilant for new algorithms that could emerge unexpectedly, as Shor himself notes there are likely many more to be discovered.

‍

Highlights:

1. Upgraded Shor-Algorithm accelerates Quantum Threat: Oded Regev's* speed boost for Shor’s* revolutionary quantum factorization algorithm significantly increases the threat to today’s asymmetric key distribution we all use daily.
2. New frontiers in quantum cryptanalysis: The improvement by extending Shor’s algorithm to multiple dimensions is profound. The number of elementary logical steps in the quantum part of Regev’s algorithm is proportional to n^1.5 when factoring an n-bit number, rather than n^2 as in Shor’s algorithm.
3. 30 years undiscovered: “This variant of my algorithm was undiscovered for 30 years and came out of the blue,” Shor said. “There’s still probably lots of other quantum algorithms to be found.”
4. Open-minded scientists: “The broader lesson of Regev’s new algorithm, beyond the implications for factoring, is that quantum computing researchers should always be open to surprises, even in problems that have been studied for decades.

*Oded Regev: computer scientist, from New York University.*Peter Shor: Professor at Massachusetts Institute of Technology.