There’s lot of excitement in quantum computing lately, driven by a new result on error correction which could bring down the requirement for total number of qubits to break commercial encryption (particularly RSA-2048). Commercial encryption is critical to much of the internet economy and financial networks and breaking it will be a big deal.
First up, one must first recognize what hasn’t changed. Peter Shor showed theoretically that Quantum computers could be extremely effective at breaking certain kinds of encryption schemes in 1994. While the methods for implementing it have been refined, the algorithm itself imposes a hard “mathematical floor.” This is visible in the requirement for logical qubits, which has remained remarkably stubborn for two decades:
2003: ~4,000 logical qubits (Beauregard)
2025: ~1,000 logical qubits (Gidney)
The complexity of factoring a 2048-bit integer simply demands a minimum amount of “perfect” information storage that just cannot be compressed away. But it’s extremely hard to obtain perfect logical qubits. For actual implementation with real hardware, we have a noisy workaround called physical qubits.
In 2012, the estimates for the total number of physical qubits required to do the job of 4000 logical qubits was around 1 Billion. However, there is also much potential for improvement and the requirements have dropped by four orders of magnitude in a decade. This is where the focus of hardware engineering has shifted. Google’s major Quantum announcement last year included the fact that they were finally able to realize one logical qubit and the total error decreased as they added more physical qubits.
The new result on Quantum Low-Density Parity-Check (qLDPC) codes represent the next theoretical evolution in fault-tolerant quantum computing. By attempting to move beyond the physical constraints of traditional surface codes, this proposed architecture aims to reduce qubit overhead significantly.
Surface codes: > 20 million physical qubits
qLDPC codes: 100,000 physical qubits
Interestingly, the traditional frontrunner (superconducting qubits architecture) is not well suited to qLDPC codes since qLDPC requires 3D-circuits. So while this opens up space for new competing architectures (neutral atoms, trapped-ion, photonics) it doesn’t immediately change forecasts for when breaking encryption becomes feasible. But things are changing quickly and the race for supremacy is on.
Co-written with @Kiran Krishnan who also did the analysis and fact-checking on this.