Building upon a groundbreaking algorithm, researchers have introduced a method for developing a more compact and noise-resistant quantum factoring circuit intended for cryptographic applications.
The last email you sent was probably encrypted using a reliable method that operates on the premise that even the fastest computer cannot efficiently factor a large number.
In contrast, quantum computers are designed to quickly dismantle intricate cryptographic systems that classical computers might struggle with indefinitely. This capability is founded on a quantum factoring algorithm proposed by Peter Shor in 1994, who is now a professor at MIT.
Despite significant advancements over the past three decades, scientists have yet to construct a quantum computer robust enough to execute Shor’s algorithm.
While some researchers are focused on creating larger quantum computers, others have been working to refine Shor’s algorithm so it can function on a smaller quantum circuit. Approximately a year ago, Oded Regev, a computer scientist at New York University, suggested a significant theoretical enhancement that would enable faster execution of the algorithm; however, it would require more memory.
Building on those advancements, researchers at MIT have proposed an approach that merges the speed of Regev’s algorithm with the memory efficiency of Shor’s. Their new algorithm matches Regev’s speed, utilizes fewer qubits (the fundamental units of quantum circuits), and has a greater resilience against quantum noise, making its practical implementation more viable.
In the future, this new algorithm could aid in creating innovative encryption techniques capable of resisting the decryption abilities of quantum computers.
“If we do eventually build large-scale quantum computers, then traditional factoring methods will become obsolete, and we’ll need alternative solutions for cryptography. But how serious is this risk? Can quantum factoring truly be made practical? Our research could potentially move us closer to real-world application,” explains Vinod Vaikuntanathan, the Ford Foundation Professor of Engineering and a senior author of a paper detailing the algorithm.
Seyoon Ragavan, a graduate student from the MIT Department of Electrical Engineering and Computer Science, is the lead author on the paper. The findings will be showcased at the 2024 International Cryptology Conference.
Decrypting encryption
To transmit messages securely across the internet, providers like email services and messaging applications generally depend on RSA, an encryption method created by MIT researchers Ron Rivest, Adi Shamir, and Leonard Adleman during the 1970s (hence the acronym “RSA”). This system is based on the belief that factoring a 2,048-bit integer (a number comprising 617 digits) is too complex for any computer to achieve in a reasonable timeframe.
This notion was overturned in 1994 when Shor, then at Bell Labs, unveiled an algorithm showing that a quantum computer could factor numbers quickly enough to compromise RSA encryption.
“That was a pivotal moment. However, in 1994, no one had a clear idea of how to construct a sufficiently large quantum computer, and we’re still not there yet. Some people question whether these machines will ever be built,” notes Vaikuntanathan.
A quantum computer would require around 20 million qubits to effectively run Shor’s algorithm, while the largest quantum computers today have approximately 1,100 qubits.
A quantum computer performs tasks through quantum circuits, much like how classical computers utilize classical circuits. Each quantum circuit consists of a sequence of operations termed quantum gates. These gates use qubits—the smallest units of a quantum computer—to execute calculations.
However, quantum gates create noise, so minimizing their usage can enhance a machine’s efficiency. Researchers have been working hard to refine Shor’s algorithm for it to operate on a smaller circuit that requires fewer quantum gates.
This was exactly what Regev accomplished with his circuit design last year.
“This was significant because it marked the first real advancement to Shor’s circuit since 1994,” says Vaikuntanathan.
The circuit designed by Shor is proportionate in size to the square of the number being factored. Therefore, to factor a 2,048-bit integer, the circuit would need millions of gates.
While Regev’s circuit demands far fewer gates, it necessitates many more qubits to provide adequate memory, presenting another challenge.
“In essence, different types of qubits can be somewhat like apples or oranges. If they are kept too long, they start to degrade. Therefore, minimizing the number of qubits in use is crucial,” explains Vaikuntanathan.
After attending a workshop where Regev discussed his research last August, Vaikuntanathan felt inspired by Regev’s closing question: Could someone refine his circuit to require fewer qubits? Vaikuntanathan and Ragavan decided to pursue this inquiry.
Quantum bouncing
To factor an extremely large number, a quantum circuit may need to execute a series of operations repeatedly, which involve computing large powers, such as 2 raised to the power of 100.
However, calculating these enormous powers can be taxing and challenging on a quantum computer, as they can only carry out reversible operations. Since squaring a number is not reversible, more quantum memory must be added with each squaring operation.
The MIT team devised an innovative approach to calculating exponents utilizing a series of Fibonacci numbers, which involves simple multiplication (a reversible process) in place of squaring. Their method only needs two quantum memory units for any exponent computation.
“It’s somewhat like a ping-pong game, where we commence with a number and alternate back and forth, multiplying between two memory registers,” adds Vaikuntanathan.
They also addressed the issue of error correction, as both Shor’s and Regev’s circuits require absolute accuracy for each quantum operation to succeed. However, achieving error-free quantum gates in reality is highly unrealistic.
Tackling this, the researchers implemented a technique to filter out erroneous outputs and focus exclusively on the correct ones.
The final outcome is a circuit that is vastly more memory-efficient, and their error correction approach enhances the algorithm’s practicality.
“The authors successfully address the two main obstacles of earlier quantum factoring algorithms. Although still not ready for immediate application, their work advances the feasibility of quantum factoring algorithms,” adds Regev.
Looking ahead, the researchers aim to improve the efficiency of their algorithm further and eventually test factoring on an actual quantum circuit.
“The crucial question following this research is: Does it bring us any closer to breaking RSA encryption? That remains uncertain; the current improvements only become relevant for integers significantly larger than 2,048 bits. Can we enhance this algorithm to handle 2,048-bit integers better than Shor’s?” queries Ragavan.
This research is supported by an Akamai Presidential Fellowship, the U.S. Defense Advanced Research Projects Agency, the National Science Foundation, the MIT-IBM Watson AI Lab, a Thornton Family Faculty Research Innovation Fellowship, and a Simons Investigator Award.
