Building on a groundbreaking algorithm, researchers have proposed a method to create a more compact and noise-resistant quantum factoring circuit for cryptography. The encryption in your most recent email likely relies on a robust method that assumes even the fastest classical computer would struggle to efficiently factorize a large number.

Quantum computers, however, have the potential to quickly break complex cryptographic systems that traditional computers might never solve. This potential is based on a quantum factoring algorithm developed in 1994 by Peter Shor, now a professor at MIT. Despite significant progress over the past 30 years, scientists have yet to develop a quantum computer powerful enough to execute Shor’s algorithm effectively.

Figure 1. Advancing Quantum Computers for Cryptography

While some researchers focus on building larger quantum computers, others aim to enhance Shor’s algorithm to run on a smaller quantum circuit. About a year ago, Oded Regev, a computer scientist at New York University, proposed a significant theoretical improvement. His revised algorithm could operate faster, although it would require a circuit with increased memory capacity. Figure 1 shows Advancing Quantum Computers for Cryptography.

Building on these findings, MIT researchers have proposed a hybrid approach that merges the speed of Regev's algorithm with the memory efficiency of Shor's. This new algorithm maintains the rapid processing speed of Regev’s method while requiring fewer quantum bits, or qubits, and demonstrating greater resistance to quantum noise. This could make it more practical to implement in real-world applications. In the long term, this algorithm could help develop new encryption techniques that are resilient to the decryption capabilities of quantum computers.

“If large-scale quantum computers are ever constructed, traditional factoring methods will become obsolete, and we will need new cryptographic solutions. But how imminent is this threat? Can we make quantum factoring viable? Our work might bring us a step closer to achieving a practical quantum factoring solution,” explains Vinod Vaikuntanathan, the Ford Foundation Professor of Engineering, a member of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), and the senior author of the paper outlining the algorithm. The paper's lead author, Seyoon Ragavan, is a graduate student in the MIT Department of Electrical Engineering and Computer Science. The research is set to be presented at the 2024 International Cryptology Conference.

Breaking Cryptography

To securely transmit messages over the internet, service providers like email clients and messaging apps typically rely on RSA, an encryption scheme developed by MIT researchers Ron Rivest, Adi Shamir, and Leonard Adleman in the 1970s (hence the name “RSA”). The security of RSA is based on the difficulty of factoring a 2,048-bit integer (a number with 617 digits), which is currently too complex for a classical computer to solve in a reasonable amount of time.

This assumption was challenged in 1994 when Peter Shor, then at Bell Labs, introduced an algorithm demonstrating that a quantum computer could factor such large numbers quickly enough to break RSA cryptography. “That was a turning point. But in 1994, nobody knew how to build a large enough quantum computer. And we’re still pretty far from there. Some people wonder if they will ever be built,” says Vinod Vaikuntanathan.

It's estimated that a quantum computer would require about 20 million qubits to run Shor’s algorithm effectively. Currently, the largest quantum computers have around 1,100 qubits. A quantum computer operates using quantum circuits, similar to how a classical computer uses classical circuits. Each quantum circuit consists of a series of operations known as quantum gates, which manipulate qubits, the fundamental units of a quantum computer, to perform calculations.

However, quantum gates introduce noise, so reducing the number of gates would improve a quantum computer's performance. Researchers have been working to refine Shor’s algorithm to enable it to run on a smaller circuit with fewer quantum gates, making it more feasible for practical use.

That's exactly what Regev achieved with the circuit he proposed a year ago.

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

Shor's original quantum circuit has a size that scales proportionally to the square of the number being factored. This means that factoring a 2,048-bit integer would require a circuit with millions of quantum gates.

Regev's circuit, on the other hand, uses significantly fewer quantum gates but requires a much larger number of qubits to provide sufficient memory. This introduces a new challenge.

“In a sense, some types of qubits are like perishable goods; if you keep them around, they decay over time. You want to minimize the number of qubits you need to keep around,” Vaikuntanathan explains.

He heard Regev discuss his findings at a workshop last August. At the end of the talk, Regev posed a question: Could someone refine his circuit to reduce the number of required qubits? Vaikuntanathan and Ragavan decided to tackle that question.

Quantum Ping-Pong

To factor large numbers, a quantum circuit needs to perform many operations, often involving computing large powers. This is challenging because quantum computers can only perform reversible operations. Squaring a number isn't reversible, so it demands additional quantum memory.

MIT researchers have developed a method that uses Fibonacci numbers to compute exponents through simple multiplication, which is reversible. This approach requires only two quantum memory units.

Their technique also addresses error correction, crucial for practical use, by filtering out incorrect results, making the circuit more memory-efficient and practical.

While the algorithm isn't yet practical for small integers like 2,048-bit numbers, it represents significant progress toward making quantum factoring more feasible. The research was funded by multiple sources, including an Akamai Presidential Fellowship and the U.S. Defense Advanced Research Projects Agency.

Source:MIT News

Cite this article:

Janani R (2024), Advancing Towards a Quantum Computer for Code-Breaking, AnaTechmaz, pp.155