Quantum computers don’t need to be nearly as powerful as we thought to break the world’s most secure encryption algorithms, scientists warn.
New research claims that quantum computers can make widely used cryptographic security systems obsolete with far fewer quantum bits, or qubits, than scientists have widely predicted — leaving sensitive data, like banking information and private messages, thought to be protected by encryption, open to interception.
One example of such a calculation is Shor’s algorithm. This quantum algorithm, designed in 1994 by mathematician Peter Shor, can efficiently factorize large numbers. It was the first evidence that quantum computers could theoretically outperform classical computers in a practical problem.
Because it is virtually unbreakable by classical means, it has become the basis for RSA public-key encryption, which is behind many of the world’s leading encryption schemes.
Scientists previously assumed that you would need a system with millions of qubits to break Shor’s algorithm using a quantum computer — a far cry from today’s best processors, which have just hundreds of qubits. But now, a surprising new study uploaded March 31 to the arXiv preprint database warns it could be viable to solve this algorithm with a system that has just 10,000 qubits.
Worse yet, the authors argue that a quantum computer with just 26,000 qubits could take as little as seven months to crack RSA-2048 encryption, the industry encryption standard used to protect most digital certificates on the internet.
Building error-free quantum computers
The reason behind this shift from needing a system with millions of qubits to just tens of thousands comes down to improvements in the field of quantum error correction (QEC) and the increased robustness of neutral-atom quantum computers, the scientists said.
Unlike classical bits, qubits are inherently “noisy,” meaning they have a much higher error rate — 1 in 1 million million versus 1 in 1,000. This makes qubits far more likely to fail during calculations, with scientists saying that future systems need millions of qubits to outpace classical computers, rather than the hundreds of qubits fitted into today’s state-of-the-art systems.
One method of reducing error rates is to use logical qubits. These are collections of entangled physical qubits that share the same data, meaning that if one of the constituent physical qubits fails, the data exists elsewhere and calculations may continue running uninterrupted.
QEC projects aim to engineer qubits and software layers that make quantum computers less prone to errors, meaning fewer qubits are needed in a fault-tolerant system to achieve comparable performance levels.
Neutral-atom quantum computers, meanwhile, are powered by qubits that are individual, charge-neutral atoms (normally, elements like rubidium, cesium or ytterbium) held in suspension by focused laser beams (known as optical tweezers) and cooled to near absolute zero.
Neutral-atom quantum computers are an alternative to conventional superconducting qubits used in the processors made by major companies like IBM, Microsoft and Google, and the study authors cited these systems as prime candidates for fault-tolerant quantum computing due to QEC advances.
Specifically, physical qubits can participate in many logical qubits, not just one, theoretically cutting the number of qubits needed for one logical qubit from hundreds or thousands to as few as five.
“Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits,” the scientists wrote in the study, which has not been peer-reviewed yet.
“Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales,” they added. “More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications.”
Solving the toughest encryption algorithms
In the study, the scientists proposed several new architectures for fault-tolerant quantum computers and analyzed performance with different error-correction mechanisms.
Existing neutral-atom machines with 500 qubits, as well as 6,000-qubit arrays, have both demonstrated “below-threshold” operation. This means that once you apply QEC, increasing the number of qubits exponentially reduces the error rate — so the bigger the system is, the more error-correction compounds to render the quantum computer fault-tolerant. This is the opposite of applying no error-correction techniques, where error rates exponentially rise as you increase the qubit count in a quantum computer.
In the study, the researchers extrapolated the potency of existing quantum computing systems and projected how powerful they would need to be to pose a threat to our cryptographic systems. They examined three key cryptographic algorithms: Shor’s algorithm, which is now a benchmark for quantum computing performance; ECC-256,a modern-but-less-complex form of cryptography that’s used to secure internet traffic and protect cryptocurrency; and the widely-used RSA-2048.
They indicated in the study that, with no error correction applied, state-of-the-art quantum computers would need 1 million qubits to crack RSA in one week, while ECC would require only 500,000 qubits and tens of minutes to solve.
Based on the calculations in the study, Shor’s algorithm would be solvable with a system fitted with just 11,961 qubits. A system with between 10,000 and 26,000 qubits could crack ECC-256 within 10 days, and a machine with between 11,000 and 14,000 qubits could solve RSA-2048 in under three years.
The researchers also predicted that parallelized architectures with approximately 102,000 qubits would crack RSA-2048 encryption in 97 days.
Although future quantum processors with thousands of logical qubits “will unlock a wide variety of applications with significant scientific and economic value,” the scientists wrote, these findings suggest we must take urgent measures to shift away from standard encryption. Google engineers, for example, say the world has less than three years to migrate to post-quantum cryptography.
It’s worth noting that the study focused only on current QEC, leaving the door open to smaller systems achieving the same feats should other techniques improve. The scientists pointed out that improved physical qubit fidelities — designing physical qubits that are inherently less error-prone by nature — or algorithmic compression — further reducing the physical qubits required — are among the breakthroughs likely to be achieved in the coming years — meaning halving the number of qubits needed in future encryption-busting systems.
“These findings have significant implications. Although substantial expertise, experimental development effort, and architectural design are required, our theoretical analysis suggests that a neutral atom system capable of implementing Shor’s algorithm could be constructed,” they wrote. “This conclusion underscores the importance of ongoing efforts to transition widely-deployed cryptographic systems toward post-quantum standards designed to be secure against quantum attacks.”
Think you know the world of computers? Test your knowledge with our computing quiz!
