Code-breaking quantum computers take a big step closer to becoming a reality

In the world of digital security, your most recent email likely benefited from tried-and-true encryption methods. These methods hinge on the idea that even the fastest classical computers cannot easily factorize enormous numbers. But quantum computers, with their radically different approach, promise to change the concepts of encryption and code-breaking forever.

Dr. Peter Shor, a prominent MIT professor, set the quantum computing world abuzz in 1994 with his quantum factoring algorithm.

His work suggested that quantum computers could one day unravel cryptographic systems like RSA, which are designed to be virtually uncrackable by conventional means.

However, despite significant advancements in the past three decades, scientists have yet to build a quantum computer capable of executing Shor’s algorithm at a practical scale.

Quantum computers: From theory to practice

Researchers are now exploring ways to make quantum factoring practical even with smaller quantum systems. About a year ago, New York University’s Oded Regev proposed an innovative theoretical improvement.

His algorithm promised faster computation but required more memory. This development was a major step forward, but it introduced a new challenge: the increased memory demands.

Building on Regev’s work, a team from MIT has recently introduced a hybrid approach that merges the speed of Regev’s algorithm with the memory efficiency of Shor’s.

This new algorithm is as swift as Regev’s but uses fewer quantum building blocks, known as qubits, and is better at handling quantum noise. The result? A potentially more feasible implementation of quantum factoring.

“If large-scale quantum computers ever get built, then factoring is toast and we have to find something else to use for cryptography,” says Vinod Vaikuntanathan, the Ford Foundation Professor of Engineering and a member of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL).

“But how real is this threat? Can we make quantum factoring practical? Our work could potentially bring us one step closer to a practical implementation.”

Understanding RSA and quantum threats

To grasp the significance of these advancements, let’s take a closer look at RSA encryption. Developed by MIT’s Ron Rivest, Adi Shamir, and Leonard Adleman in the 1970s, RSA encryption relies on the complexity of factoring large numbers.

For example, factoring a 2,048-bit integer — essentially a number with 617 digits — would take an impractically long time for classical computers.

This scenario changed in 1994 when Shor’s algorithm demonstrated that a sufficiently powerful quantum computer could factor these large integers efficiently.

This revelation was a game-changer, though at the time, building such a quantum computer was far from achievable, and it remains so today.

Estimates suggest that a quantum computer would need around 20 million qubits to run Shor’s algorithm effectively. Currently, the most advanced quantum computers have about 1,100 qubits.

Quantum computers and the circuit puzzle

Quantum computers operate using quantum circuits, which consist of operations performed by quantum gates. These gates manipulate qubits to perform calculations.

However, the introduction of quantum noise complicates things. More gates lead to more noise, so researchers are striving to improve algorithms to work with fewer gates.

Regev’s algorithm from a year ago was significant because it reduced the number of quantum gates required, though it increased the number of qubits needed. This raised a new issue: managing memory efficiently with a high qubit count.

In response, MIT’s research team, led by Seyoon Ragavan, developed an approach that combines the speed of Regev’s algorithm with the memory efficiency of Shor’s.

Their method reduces the number of qubits required and has better tolerance to quantum noise. This advancement is crucial for making quantum factoring more practical.

Efficiency and error correction

The MIT researchers addressed two major challenges: the need for extensive quantum memory and error correction. Quantum computations often involve large powers, which can be cumbersome to perform on quantum systems due to their need for reversible operations.

Instead of using squaring, which is not reversible, the MIT team employed Fibonacci numbers to simplify the process, needing only two quantum memory units.

Error correction is another hurdle. Quantum circuits are highly sensitive to errors, and traditional quantum gates must function perfectly. The MIT team developed a technique to filter out erroneous results, making the algorithm more reliable and feasible.

“This work resolves the two most critical bottlenecks in earlier quantum factoring algorithms. Although it is not yet practical, it brings us closer to realizing quantum factoring algorithms,” adds Regev.

What the future holds

The next steps for this research involve further improving the algorithm and testing it on actual quantum circuits. The ultimate question remains: Will this progress bring us closer to breaking RSA encryption?

As Ragavan notes, “The elephant-in-the-room question after this work is: Does it actually bring us closer to breaking RSA cryptography? That is not clear just yet; these improvements currently only kick in when the 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?”

As the field of quantum computing continues to evolve, these innovations offer a glimpse into a future where our digital security could be reshaped by the very technology that aims to challenge it.

The full study was published in the journal arXiv.

—–

Like what you read? Subscribe to our newsletter for engaging articles, exclusive content, and the latest updates.

Check us out on EarthSnap, a free app brought to you by Eric Ralls and Earth.com.

—–