Quantum computers could break RSA encryption with fewer than a million qubits

Breaking encryption with a quantum computer just got 20 times easier

New estimate slashes quantum requirements for cracking RSA, raising urgency for cybersecurity transition

The longstanding assumption that modern encryption methods are safe from decryption may be on the verge of collapse — at least in a quantum future. A new study by Google Quantum AI researcher Craig Gidney has shown that cracking RSA encryption — the backbone of digital security for email, banking, and state secrets — could require just under a million qubits, rather than the previously estimated 20 million.

Although no quantum computer today comes close to this capability, the revision slashes prior estimates by a factor of 20 and marks a significant milestone in quantum algorithm optimization.

Shor’s algorithm: the key to cracking RSA

At the core of the breakthrough is Shor’s algorithm, a quantum method discovered in 1994 that can factor large numbers exponentially faster than classical computers. Since RSA encryption is built on the difficulty of such factoring, the algorithm presents a looming threat to cybersecurity.

In a 2019 paper, Gidney had calculated that breaking a 2048-bit RSA key — a common standard — would require a quantum machine with around 20 million qubits and eight hours of runtime. But his latest work, which has yet to be peer-reviewed, demonstrates that recent advances in quantum compilation and error correction bring that number down to less than one million qubits, though with a longer runtime of up to one week.

“This is a serious update — not because a million-qubit machine is around the corner, but because it’s much closer than we thought,” says Peter Leek, a quantum physicist at the University of Oxford.

Post-quantum cryptography now more urgent

The development has accelerated calls for a global transition to post-quantum cryptography, encryption systems believed to be resistant to quantum attacks. The U.S. National Institute of Standards and Technology (NIST) has already begun selecting new algorithms for standardization, preparing for the eventual need to replace RSA and similar systems.

“This new research doesn’t change our announced migration timelines, but we’re keeping an eye on things,” says Dustin Moody of NIST. “Government and industry are already working on the transition.”

For context, previous government initiatives around algorithmic modernization have already shown how complex — and politically sensitive — such technology shifts can be.

A new balance between qubits and runtime

Gidney’s reduced estimate is not based on new theoretical discoveries, but rather on optimizing how Shor’s algorithm is compiled into physical operations — and accepting a longer computation time as a trade-off.

“There’s a whole parameter space between memory and time,” says quantum theorist Aleks Kissinger, also at the University of Oxford. “Gidney found a very compelling combination of space and time, where both look pretty reasonable.”

Essentially, if future quantum machines can’t scale up to 20 million qubits, they might still succeed by running longer and using more sophisticated scheduling of operations.

The million-qubit milestone: closer than it seems?

While the best current quantum machines operate at just over 1000 qubits, researchers say the real barrier lies in error correction — the ability to maintain qubit stability long enough to complete complex operations. More efficient techniques in this area could reduce the physical qubit requirement even further.

Leek believes this estimate is far from final. “I wouldn’t expect this to be the final implementation. Future approaches may not need a million qubits if we improve quantum error correction. That target is within reach.”

In other words, the path to breaking encryption isn’t science fiction — it’s an engineering challenge, and one that may be solved sooner than many expect.

Stay tuned to The Horizons Times as we track breakthroughs in quantum computing and their impact on security, data privacy, and the future of digital infrastructure.