Breakthrough quantum algorithm could break advanced data encryption

MIT researchers have achieved a breakthrough in quantum computing.

They developed a new algorithm that could enable quantum machines to quickly break the encryption methods that currently protect our digital world.

It also highlights the importance of developing new quantum-resistant encryption methods.

The research, led by Vinod Vaikuntanathan and graduate student Seyoon Ragavan, focuses on making quantum factorization more practical.

For context, quantum factorization is a process that can defeat widely used encryption systems like RSA.

Threats to RSA encryption

RSA encryption is the basis of digital communication. The security of RSA encryption derives from the inherent difficulty for classical computers to factor large numbers.

“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,” the researchers explained in a press release.

However, quantum computers have the theoretical ability to exploit the unique principles of quantum mechanics to perform this factorization much faster. However, quantum computers are not without their drawbacks. The main challenges they face include noise and resource constraints.

According to the press release, a quantum circuit aimed at factoring very large numbers would need to perform multiple runs, including operations to calculate powers such as 2 to the power of 100.

“However, because quantum computers can only perform reversible operations, performing such large operations on a quantum computer would be costly and difficult,” he explains.

“Squaring a number is not a reversible operation, so every time you square a number you need to add more quantum memory to compute the next square.”

Simplifying the calculations

The researchers discovered a method to calculate the exponent using a series of Fibonacci numbers, which requires only simple, reversible multiplications instead of squaring. Crucially, only two quantum memory units are needed to calculate the exponent.

“It’s like a game of ping-pong, where you start with a number and bounce it back and forth while multiplying it between two quantum memory registers,” Vaikuntanathan emphasized.

Moreover, quantum computers work using quantum circuits made up of quantum gates, which can be noisy and introduce errors, but error-free quantum gates are impossible to achieve in real machines.

The team solved this problem by employing techniques to filter out corrupted results and ensure that only correct results are processed.

“The end result is circuits with significantly improved memory efficiency. Additionally, their error correction techniques make the deployment of their algorithms more practical,” the press release claims.

The way forward

This breakthrough is a big step towards practical quantum factorization, but implementation on real quantum hardware remains a future goal.

Current quantum computers lack the capabilities necessary to run such complex algorithms.

But as New York University computer scientist Oded Regev pointed out, the MIT team’s work “brings quantum factorization algorithms closer to reality.”

This development highlights the urgent need to develop new cryptosystems that are resistant to quantum attacks.

As quantum computers continue to evolve, advances like this one bring us closer to a future where quantum machines pose a real threat to current encryption standards.