New estimates for breaking encryption with a quantum computer

Hi there,

How did we go from needing a billion qubits to 10,000 for breaking encryption?

Two papers dropped this week. One from Google Quantum AI, one from the new startup Oratomic (whose team includes John Preskill and Dolev Bluvstein). Both update the resource estimates for running Shor's algorithm (the quantum algorithm that can factor large numbers and solve the math underlying most public-key cryptography) at cryptographically relevant scales.

Much of the coverage focused on the qubit count dropping. And it has dropped, dramatically. But beyond the headlines, I want to dig into the details: what these results actually assume, where the remaining bottlenecks are, and what this means for the field. Not just for the ones fearing for their Bitcoin.

Early quantum computing architectures pointed toward needing a billion physical qubits to break encryption like RSA-2048 (the widely used system where security relies on the difficulty of factoring large numbers). The Oratomic result now brings the requirement for ECC-256, elliptic curve cryptography with a 256-bit key, the type of encryption that secures most modern digital signatures including Bitcoin and Ethereum transactions, down to roughly 12,000 physical qubits in a neutral-atom architecture.

For context: physical qubits are the actual hardware units; logical qubits are the error-protected "ideal" qubits you compute with, and you always need many physical qubits to encode each logical one.

The compression comes from switching error-correcting codes. Surface codes, the workhorse of the past decade, give you about a 4% encoding rate. This is the code family Google has been focusing on with their superconducting qubits, and it's well-understood: there's a mature toolchain for performing operations, called lattice surgery, where you "cut and stitch" neighboring 2D patches of qubits to perform logical gates.

Neutral-atom architectures have a key structural advantage here: atoms held in optical tweezers can be physically rearranged, giving you all-to-all connectivity. Any qubit can interact with any other. This unlocks so-called nonlocal encodings, where a single code block can protect many logical qubits at once rather than just one. Over the past years, we've seen the rise of quantum LDPC codes (qLDPC, short for "low-density parity-check" codes, meaning each physical qubit only participates in a small number of error checks, which keeps the hardware demands manageable). The field is heavily doubling down on this direction, including the Oratomic team. The high-rate qLDPC codes in their paper hit approximately 28 to 30% encoding rate. That's roughly seven times more logical qubits per physical qubit compared to the surface code.

A better encoding rate doesn't automatically give you a machine that can run an algorithm. The hard part is actually doing universal computation on these codes.

Surface codes run gates through lattice surgery, a relatively well-understood toolchain built up over years. You're working with small, independent patches of qubits, and each logical qubit lives in its own patch. To perform a gate between two logical qubits, you physically merge and split neighboring patches. It's conceptually clean and geometrically local.

qLDPC codes are fundamentally different. Each logical qubit is spread across the entire code block. It's a nonlocal encoding by design. You can't just merge neighboring patches because there are no separate patches. Instead, you need something called code surgery: you construct an auxiliary set of qubits (an "ancilla system") that temporarily couples to the full code block in order to measure the logical operator you care about. The ancilla system has to be carefully designed so that the merged code maintains its error-correcting distance. Otherwise you've gained nothing. The overhead of these ancilla systems scales with the code's parameters, making the construction and optimization of surgery gadgets a real theoretical and engineering challenge. This is an active area of research, and the Oratomic team's paper presents constructions and benchmarks for these surgery gadgets.

In order to actually compute, the Oratomic team divides their neutral-atom quantum computer into four functional zones: a memory zone for storing logical qubits during computation, a processor zone for active computation, an operation zone for performing Clifford operations (the "easy" quantum gates that don't require special resources), and a resource zone for generating magic states. Magic states are special quantum states that, when consumed, allow the computer to perform non-Clifford gates, the gates that are actually hard to do fault-tolerantly but essential for universal quantum computation.

This last zone is where the heavy lifting happens for cryptographic circuits, because the critical operations (Toffoli gates, a key three-qubit gate used heavily in arithmetic circuits like the modular exponentiation inside Shor's algorithm) are implemented by consuming these magic states.

The total runtime of the algorithm is dominated by the total Toffoli gate count multiplied by the cost per Toffoli. In the Oratomic balanced architecture, each Toffoli requires roughly 19 × 2d/3 stabilizer cycles (a stabilizer cycle is one round of error-checking measurements across the code block), where d is the code distance (higher distance means better error protection but more cycles).

At 1 ms per stabilizer cycle, which is realistic but optimistic for current neutral-atom hardware, the full algorithm for ECC-256 on the most qubit-efficient architecture (11,961 qubits) takes on the order of hundreds of days. That's sequential execution: one Toffoli at a time.

To make it more practical, Oratomic proposes parallelizing the Toffoli execution across multiple resource state factories. This bumps the qubit count to ~26,000 but brings the ECC-256 runtime down to about 10 days. RSA-2048 is roughly two orders of magnitude harder due to much larger circuit depth: the time-efficient construction needs ~102,000 qubits and still takes about 97 days.

These are all 1 ms cycle time numbers. Slow-clock, neutral-atom timescales. Not the ~1 µs you get from a superconducting device. That three-orders-of-magnitude speed difference is exactly where the Google paper enters the picture.

The Google Quantum AI numbers sit on the other end of the hardware spectrum. Their resource estimates for secp256k1, the specific elliptic curve underlying Bitcoin and Ethereum's digital signatures, are notable: 1,200 logical qubits and 90 million Toffoli gates (low-qubit variant), or 1,450 logical qubits and 70 million Toffoli gates (low-gate variant). This represents roughly a 10x improvement in spacetime volume over the most efficient prior work on a single ECDLP instance.

Translated to superconducting hardware with surface codes at 10⁻³ physical error rates, that's under 500,000 physical qubits. For comparison, prior estimates for ECDLP-256 were in the millions of physical qubits (Litinski 2023 estimated ~9 million in a photonic architecture). On the RSA side, estimates have dropped from ~1 billion qubits (2012) to under 1 million (Gidney, 2025).

Google introduces an important concept here: a "primed" quantum computer that precomputes the first half of Shor's algorithm (which only depends on public protocol parameters common to all addresses) and then waits. Once a public key appears, say when someone broadcasts a Bitcoin transaction, the primed machine only needs to solve the second half. From that primed state, the runtime is about 9 minutes on a superconducting CRQC (cryptographically relevant quantum computer). Uncomfortably close to Bitcoin's average 10-minute block time.

What strikes me about these two papers together is not just the numbers dropping. It's that we now have two completely different hardware architectures converging on the same conclusion from different directions. Neutral atoms with qLDPC codes pushing physical qubit counts into the low thousands at the cost of long runtimes. Superconducting qubits with surface codes accepting higher qubit counts but clocking in at minutes, not months.

The Oratomic numbers assume 1 ms cycle times that haven't been demonstrated at scale. The Google numbers assume half a million physical qubits with 10⁻³ error rates on a planar chip, which is still well beyond what anyone has built. But the trajectory is clear, and the pace of improvement over the past year has been faster than most people expected.

If you work in quantum computing, this is a moment to pay attention to the engineering gaps that remain, not just the headline qubit counts. If you work in cryptography or hold crypto assets, the migration to post-quantum cryptography is no longer a theoretical concern for the distant future. Google's paper puts it bluntly: the cryptocurrency community should begin preparing against quantum attacks immediately.

Until next time,
Michaela

Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits

Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations

Thumbnail: Quanta Magazine