New advances in quantum computing: mit researchers develop revolutionary algorithm to effectively factorize large numbers with reduced memory requirements

Recently sent email was likely protected using an established encryption method that relies on the fact that even the fastest computer could not simply factorize very large numbers.

However, quantum computers open a new dimension in computing, promising to quickly break complex cryptographic systems that would take classical computers millions of years to crack. This new capability is based on a quantum factoring algorithm first proposed by Peter Shor in 1994. His work, although revolutionary, has not yet been fully realized due to technical challenges in building sufficiently powerful quantum computers.

Research in the field of quantum computing science continues intensively, and scientists around the world are working to improve Shor's algorithm to make it suitable for use on smaller and currently available quantum computers. Last year, computer scientist Oded Regev from New York University proposed a significant theoretical improvement to Shor's algorithm, which reduces the number of required quantum gates but increases memory demands.

MIT researchers, building on Regev's results, proposed a new algorithm that combines the speed advantages of Regev's approach with the memory efficiency of Shor's algorithm. This new algorithm is not only fast but also requires fewer quantum building blocks (qubits) and has greater resistance to quantum noise, making it much more feasible for implementation in real-world conditions.

Advances in quantum computing
Quantum computers differ from classical ones in their ability to use quantum bits, or qubits, which can be in multiple states simultaneously. This allows quantum computers to process vast amounts of data in parallel, significantly speeding up the solving of complex mathematical problems.

However, building large quantum computers capable of running algorithms like Shor's remains a major challenge. The most advanced quantum computers currently have around 1,100 qubits, which is far below the 20 million qubits needed to run Shor's algorithm on numbers relevant to modern cryptography.

Regev's algorithm represents a significant step forward as it reduces the number of required quantum gates, but the problem of increased memory demand remains. Qubits, which are the fundamental element of quantum computers, are prone to degradation over time, meaning their use must be optimized to achieve maximum efficiency.

New methods and challenges
MIT researchers have developed a method that uses Fibonacci numbers for exponentiation, significantly reducing the need for squaring numbers. This method requires only two quantum memory units, reducing the need for a large number of qubits and enabling complex operations with less quantum memory.

This approach resembles a game of ping-pong, where the initial value of a digit is transferred between two quantum registers, multiplying at each step. Additionally, the MIT team has developed techniques for error correction in quantum operations, which is crucial for the reliable application of these algorithms in real quantum computers.

Perspectives on quantum cryptography
Although the work of MIT researchers is a significant step forward, many challenges remain before quantum computers can threaten existing cryptographic systems like RSA. Current estimates suggest that improvements need to be applicable to numbers significantly larger than 2,048 bits, raising the question of whether this new method will be effective enough for modern encryption standards.

Despite this, the development of new algorithms and techniques for optimizing quantum computing operations lays the foundation for a future in which quantum cryptography will play a key role in protecting digital communications. Researchers believe that further improvements, combined with technological advancements, will enable the practical application of quantum computers in cryptography within the coming decades.

The MIT team intends to continue research aimed at further optimizing the algorithm, with the hope that it can one day be tested on real quantum computers. The ultimate goal is to develop encryption systems resistant to future quantum threats, ensuring the long-term security of digital data.

Source: Massachusetts Institute of Technology