The field of quantum computing is on the brink of revolutionizing cryptography as we know it, with MIT researchers pushing the envelope further. A team at MIT, as reported by MIT News, has developed an algorithm that balances the resource needs of quantum computing by combining the speed of a previously improved algorithm and the memory efficiency of an older method. This innovation is poised to be a notable leap towards practical quantum factoring, which may decode encryption systems that currently secure online transmissions.
The original algorithm, proposed by Peter Shor in 1994, set the stage for quantum computers to break cryptographic codes with efficiency far beyond the capabilities of classical computers. Although about 30 years have passed, a quantum computer robust enough to run Shor's algorithm hasn't been built yet. The largest quantum computers today hold roughly 1,100 qubits, the fundamental units of quantum computing, still a far cry from the estimated 20 million qubits needed to run the algorithm fully.
Recent advancements by Oded Regev of New York University managed to speed up the process and proposed a theoretical improvement a year ago. However, his method required more memory, which isn't ideal given that qubits, akin to perishable goods, have a limited lifespan. Reinspired by those insights, MIT researchers have proposed a new method that they claim is as rapid as Regev's and requires fewer qubits, while also having higher tolerance to quantum noise. Vinod Vaikuntanathan, an MIT professor and the senior author of the research, highlighted the significance of their work in potentially inching toward a practical quantum factoring implementation.
Seyoon Ragavan, a graduate student at MIT and lead author of the work, described a more memory-efficient quantum circuit employing a clever technique for computing exponents that contributes to the breakthrough. Using a simple multiplication of Fibonacci numbers instead of squaring, the method allows for two memory units to calculate any exponent, likening it to a "quantum ping-pong game." An added benefit is their error correction technique, designed to ignore corrupted data, which visibly enhances the algorithm's practicality. Though the question remains, as Ragavan puts it, whether these advancements actually bring us closer to solving the encryption battle posed by RSA, more work is certainly ahead to realize this goal. The research, set to be presented at the 2024 International Cryptology Conference, raises the prospect of an inflection point in cryptographic security.
While the MIT innovations provide groundwork for more secure encryption methods resilient to quantum decodings and represent a stride towards functional quantum computers, this does not instantly signal the end of RSA encryption. The MIT team's new algorithm currently applies to integers much larger than the 2,048-bit keys standard in RSA cryptography, and further refinements are necessary before the algorithm could challenge today's encryption methods. Funding for this research came from a slew of sources, including the U.S. Defense Advanced Research Projects Agency (DARPA), the National Science Foundation (NSF), and the MIT-IBM Watson AI Lab, pointing to the significant institutional interest in quantum computing's future.
