Researchers propose smaller, more noise-tolerant quantum factorization circuit for cryptography

The last email you sent was probably encrypted using a tried-and-true method that relies on the idea that even the fastest computer would be unable to efficiently factor a gigantic number into factors.

Quantum computers, on the other hand, promise to quickly crack complex cryptographic systems that a classical computer might never be able to crack. This promise is based on a quantum factorization algorithm proposed in 1994 by Peter Shor, now a professor at MIT.

But even though researchers have made great strides in the past 30 years, scientists have yet to build a quantum computer powerful enough to run Shor’s algorithm.

While some researchers are working to build larger quantum computers, others are trying to improve Shor’s algorithm so that it can run on a smaller quantum circuit. About a year ago, Oded Regev, a computer scientist at New York University, proposed a major theoretical improvement. His algorithm could run faster, but the circuit would require more memory.

Building on these results, the MIT researchers proposed an approach that combines the speed of Regev’s algorithm with the memory efficiency of Shor’s. This new algorithm is as fast as Regev’s, requires fewer quantum building blocks called qubits, and has greater tolerance for quantum noise, which could make it easier to implement in practice.

In the long term, this new algorithm could shed light on the development of new encryption methods capable of resisting the code-breaking power of quantum computers.

“If large-scale quantum computers are ever built, factorization will be a pipe dream and we will have to find another way to use cryptography. But is this threat real? Can we make quantum factorization practical?”

“Our work could potentially bring us closer to a practical implementation,” says Vinod Vaikuntanathan, a Ford Foundation professor of engineering, member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) and lead author of a paper describing the algorithm.

The study’s lead author is Seyoon Ragavan, a graduate student in MIT’s Department of Electrical Engineering and Computer Science. The research was presented at the International Conference on Cryptology 2024 (Crypto 2024).

Decrypting Cryptography

To securely transmit messages over the Internet, service providers such as email clients and messaging applications typically rely on RSA, a cryptographic system invented by MIT researchers Ron Rivest, Adi Shamir, and Leonard Adleman in the 1970s (hence the name “RSA”). The system is based on the idea that factoring a 2,048-bit integer (a 617-digit number) is too difficult for a computer to do in a reasonable amount of time.

This idea was upended in 1994 when Shor, then at Bell Labs, introduced an algorithm that proved that a quantum computer could factorize quickly enough to break RSA cryptography.

“It was a turning point. But in 1994, no one knew how to build a quantum computer big enough. And we’re still a long way from that. Some people wonder if they’ll ever be built,” Vaikuntanathan says.

It is estimated that a quantum computer would need about 20 million qubits to run Shor’s algorithm. Currently, the largest quantum computers have about 1,100 qubits.

A quantum computer performs calculations using quantum circuits, just as a classical computer uses classical circuits. Each quantum circuit is made up of a series of operations called quantum gates. These quantum gates use qubits, which are the smallest building blocks of a quantum computer, to perform calculations.

But quantum gates introduce noise, and fewer gates would improve a machine’s performance. Researchers have been working to improve Shor’s algorithm so that it can run on a smaller circuit with fewer quantum gates.

This is exactly what Regev did with the circuit he proposed a year ago.

“It was big news because it was the first real improvement to the Shor circuit since 1994,” says Vaikuntanathan.

Shor’s proposed quantum circuit has a size proportional to the square of the number to be factored. This means that if one were to factor a 2,048-bit integer, the circuit would need millions of gates.

Regev’s circuit requires far fewer quantum gates, but it needs far more qubits to provide enough memory. This poses a new problem.

“In a sense, some types of qubits are like apples or oranges. If you keep them, they degrade over time. So you want to minimize the number of qubits you have to keep,” Vaikuntanathan says.

He heard Regev talk about his results at a workshop last August. At the end of his talk, Regev asked a question: Could someone improve his circuit to require fewer qubits? Vaikuntanathan and Ragavan answered that question.

Quantum Ping-Pong

To factor a very large number, a quantum circuit would have to run many times, performing operations involving computational powers, such as 2 to the power of 100.

But calculating such large powers is expensive and difficult to do on a quantum computer, because quantum computers can only perform reversible operations. Squaring a number is not a reversible operation, so each time a number is squared, quantum memory must be added to calculate the next square.

MIT researchers have come up with a clever way to calculate exponents using a series of Fibonacci numbers that requires a simple, reversible multiplication rather than squaring. Their method requires only two units of quantum memory to calculate an exponent.

“It’s a bit like a game of ping-pong, where we start with a number and then bounce back and forth, multiplying between two quantum memory registers,” Vaikuntanathan adds.

They also addressed the challenge of error correction. The circuits proposed by Shor and Regev require that every quantum operation be correct for their algorithm to work, Vaikuntanathan says. But error-free quantum gates would be impossible on a real machine.

They overcame this problem by using a technique to filter out corrupted results and process only the good ones.

The end result is a circuit that uses much less memory. Additionally, their error correction technique would make the algorithm more practical to deploy.

“The authors solve two main problems encountered in the quantum factorization algorithm. Although their work is not yet immediately applicable, it brings quantum factorization algorithms closer to reality,” Regev adds.

In the future, the researchers hope to make their algorithm even more efficient and, one day, use it to test factorization on a real quantum circuit.

“The question with this work is: Will this actually bring us closer to breaking RSA cryptography? That’s not clear yet; these improvements currently only happen when integers are much larger than 2,048 bits. Can we push this algorithm and make it more feasible than Shor’s, even for 2,048-bit integers?” Ragavan asks.

This article is republished with kind permission from MIT News (web.mit.edu/newsoffice/), a popular site covering the latest research, innovation, and teaching at MIT.