Toward a code-breaking quantum computer

Recent advancements in quantum computing have sparked significant interest in the field of cryptography, particularly concerning the potential to break widely-used encryption methods like RSA. Traditional encryption relies on the difficulty of factoring large numbers, a task that classical computers find impractical. However, quantum computers, leveraging Shor’s algorithm proposed in 1994, could theoretically factor these large numbers efficiently, posing a threat to current cryptographic systems. Despite this potential, building a quantum computer capable of running Shor’s algorithm remains a challenge due to the need for around 20 million qubits, far beyond the capabilities of today’s largest quantum computers.

In response to this challenge, researchers have been working on improving Shor’s algorithm to make it feasible for smaller quantum circuits. A notable theoretical improvement was proposed by Oded Regev, which increased speed but required more memory. Building on Regev’s work, MIT researchers have developed a new algorithm that combines the speed of Regev’s approach with the memory efficiency of Shor’s, making it more practical by requiring fewer qubits and having higher tolerance to quantum noise. This advancement not only brings us closer to practical quantum factoring but also highlights the ongoing need to develop new encryption methods that can withstand the power of future quantum computers. The research, led by Seyoon Ragavan and Vinod Vaikuntanathan, represents a significant step toward realizing quantum factoring and will be presented at the 2024 International Cryptology Conference.