The physics of quantum computing is the easy part. The equations have been stable for a century, and the algorithm that threatens modern public-key cryptography was published in 1994. What stands between that algorithm and a broken RSA key is not theory - it is hardware that loses its quantum state in microseconds and needs on the order of a thousand physical components to protect a single reliable logical one. This is a walk up the stack: from one qubit, to the scaling story everyone gets slightly wrong, to Shor's algorithm, to the decoherence and error-correction overhead that actually decide whether the cryptographic threat is real - and where the engineering sits in 2026.

1. The qubit: amplitudes, not coin flips

A classical bit is 0 or 1. A qubit is a unit vector in a two-dimensional complex space, written as a linear combination of basis states:

|?? = ?|0? + ?|1?,   with   |?|� + |?|� = 1

The coefficients ? and ? are complex probability amplitudes - not probabilities. This distinction is the entire game. Probabilities are non-negative reals that sum to 1; amplitudes are complex numbers whose squared magnitudes sum to 1. Because amplitudes carry phase, they can interfere - adding constructively or cancelling destructively. Every quantum speedup is, at bottom, a way of engineering that interference.

Measurement applies the Born rule: you observe |0? with probability |?|� and |1? with probability |?|�, and the state collapses to whatever you saw. You never read ? and ? directly. A qubit is not "0 and 1 at the same time" in any classically useful sense - it is a phase-carrying amplitude distribution that yields a single classical bit the instant you look at it.

2. State-space scaling - and the catch nobody mentions

The popular "exponential scaling" pitch is usually stated wrong, so here it is precisely. A register of n classical bits is in exactly one of 2? states at any instant. A register of n qubits is described by a vector of 2? complex amplitudes - one per basis state - all evolving simultaneously under the system's dynamics.

  • 10 classical bits - one of 1,024 possible states at a time.
  • 10 qubits - a superposition described by 1,024 complex amplitudes evolving together.
  • 300 qubits - ? 2�?? ? 10?? amplitudes: roughly ten billion times more numbers than there are atoms in the observable universe (~10??).

Two corrections to the usual telling. First, that dimensionality comes from superposition over a tensor-product space, not from entanglement by itself. Entanglement is the property that the joint state cannot be factored into independent per-qubit states; it is necessary for quantum advantage, but the 2? amplitude count exists the moment you have n qubits in superposition. Conflating the two is the most common pop-science error in the field.

Second - and this is the catch the headline numbers omit - you cannot read out those 2? amplitudes. Measurement collapses everything to a single n-bit string. You do not get a free parallel database. The entire craft of quantum algorithm design is arranging the dynamics so that the few amplitudes encoding the answer reinforce while the rest cancel, before you measure. Exponential state space is the raw material; useful interference is the product.

3. Shor's algorithm and the real threat model

RSA's security does not rest on the difficulty of "factoring large primes" - factoring a prime is trivial. It rests on the difficulty of factoring a large semiprime: the product of two large primes. Classically, the best-known methods run in sub-exponential but super-polynomial time, which is why 2048-bit keys are considered safe today.

Shor's algorithm reframes factoring as period finding (equivalently, order finding). To factor N, pick a random base a and find the period r of the function a^x mod N. Given r, classical post-processing recovers the factors with high probability. The quantum step finds r efficiently: a superposition over inputs is pushed through modular exponentiation, then a quantum Fourier transform turns the hidden period into an interference pattern - amplitudes reinforce at frequencies tied to the period and cancel elsewhere - so a single measurement reveals it. The speedup comes from polynomial-time period finding, not from "trying every factor in parallel."

The threat is concrete but not imminent, and the resource estimates have collapsed over a decade:

  • 2019 (Gidney & Eker�): roughly 20 million noisy physical qubits, about 8 hours, to factor RSA-2048.
  • 2025 (Gidney): under 1 million noisy qubits, under a week - a ~20� reduction in qubit count, trading runtime for footprint under the same hardware assumptions.

Both assume fault-tolerant machines that do not yet exist; the largest gate-based processors today sit in the hundreds-to-low-thousands of physical qubits. The practical consequence is "harvest now, decrypt later": an adversary can record encrypted traffic today and decrypt it once the hardware arrives. That is why NIST finalized its post-quantum standards (ML-KEM for key exchange, ML-DSA and SLH-DSA for signatures) in 2024 and migration is already underway. The defensive clock started before the offensive hardware did - deliberately.

4. Decoherence: the dominant bottleneck

The reason those fault-tolerant machines don't exist yet is that qubits refuse to stay quantum. Decoherence is the loss of phase information as a qubit couples to its environment; the moment it happens, the amplitudes the algorithm depends on are scrambled. Stray microwave photons, thermal fluctuations, control-line noise, and - at the margins - cosmic-ray strikes all drive premature collapse.

Two numbers characterize the problem: T1 (energy relaxation) and T2 (phase coherence). For today's superconducting qubits these sit in the range of tens to a few hundred microseconds, and every gate in a circuit must complete well inside that window. But the "isolate it and freeze it" framing is architecture-specific, not universal:

  • Superconducting (IBM, Google) - dilution refrigerators at ~10-15 millikelvin, a hair above absolute zero.
  • Trapped ions (IonQ, Quantinuum) - only the trap is cooled; coherence times reach seconds, but gate operations are slower, capping throughput.
  • Neutral atoms and photonics (Atom Computing, PsiQuantum) - different isolation regimes again; photonic approaches target room-temperature operation outright.

So "requires a dilution refrigerator at 15 mK" describes one platform, not quantum computing in general. What is universal is the race: every architecture is fighting the clock between when a computation begins and when its quantum state decays.

5. Error correction and the overhead that decides everything

You cannot beat decoherence by copying a qubit and taking a majority vote, because the no-cloning theorem forbids duplicating an unknown quantum state. Classical triple-redundancy is simply unavailable. Quantum error correction takes a different route: it spreads the information of one logical qubit across many entangled physical qubits. Surface codes and related topological codes lay those physical qubits out on a lattice so that errors can be detected and corrected by measuring stabilizers - without ever measuring, and thus collapsing, the protected logical state.

The overhead is the whole story. The figure you'll see quoted is roughly 1,000 physical qubits per logical qubit, but that number is not a constant - it scales with the physical error rate and the target logical error rate. And one logical qubit buys you nothing: breaking RSA-2048 needs thousands of logical qubits, which is why credible projections put practical fault tolerance at tens of thousands to millions of physical qubits. The 1,000:1 ratio is the floor of a much taller building. The active research frontier is shrinking it: IBM's 2024 Nature result on quantum LDPC (bivariate-bicycle) codes claims roughly an order-of-magnitude lower overhead than surface codes - though that work demonstrated a fault-tolerant memory, not computation on the encoded data.

This is also why raw qubit-count headlines mislead. The milestone that matters is not size but whether error correction improves as you scale - historically, adding physical qubits introduced more errors than it removed. In December 2024, Google's Willow (105 qubits) crossed the "below-threshold" line: as the code lattice grew from 3�3 to 5�5 to 7�7 physical qubits, the logical error rate was suppressed by about 2� at each step instead of climbing. That was the first experimental confirmation at this scale that the theory behind fault tolerance behaves as predicted, and it was peer-reviewed - published in Nature (2024), not just a press release. That result - not any qubit count - is why 2025-2026 reads as an inflection point.

Where the hardware actually stands: IBM's Condor reached 1,121 physical qubits in 2023 and Atom Computing's neutral-atom array around 1,180, but the chips that matter for the path forward are smaller and cleaner - Google's 105-qubit Willow and IBM's 120-qubit Nighthawk (late 2025), the latter explicitly aimed at a commercially relevant "quantum advantage" demonstration within 2026. Machines large enough to threaten RSA remain a roadmap item: IBM targets fault tolerance by 2029, and at least one forecast review puts the odds of an RSA-2048-capable device arriving before 2039 below 5%. Calling large-scale fault-tolerant execution "speculative" is fair. Calling the trajectory speculative no longer is.

6. The people building it don't agree - on the record

If the timeline feels uncertain, that is because the people closest to the hardware say wildly different things in public. The useful exercise is to read each claim against the speaker's incentives.

  • IBM - Jay Gambetta is the most committed to a date: fault tolerance by 2029, via a 200-logical-qubit system ("Starling") targeting 100-million-gate circuits, built on quantum-LDPC codes IBM says cut overhead roughly tenfold versus surface codes. Gambetta has gone as far as claiming IBM has "cracked the code to quantum error correction." It is a roadmap backed by a real Nature result - but a roadmap, not a shipped machine.
  • Google - Hartmut Neven frames Willow's below-threshold demonstration as crossing the "break-even point": for the first time, adding physical qubits drove the logical error rate down instead of up. That specific claim is peer-reviewed. His separate musing that the result is evidence for a multiverse is not, and is worth filing separately.
  • Rigetti - Subodh Kulkarni puts quantum advantage three-to-five years out and full fault tolerance another seven-to-nine, betting on superconducting qubits and a chiplet architecture for manufacturing yield. He argues superconducting gate speeds - orders of magnitude faster than ion traps - are the decisive scaling advantage.
  • D-Wave - Alan Baratz rejects the entire "years away" framing, arguing useful quantum value exists today through annealing, and called D-Wave's 2025 Science result the first computational supremacy on a "useful" problem. But that claim is contested: classical-simulation groups (the Flatiron Institute's belief-propagation method; EPFL's variational Monte Carlo) reproduced parts of it - a live reminder that supremacy claims tend to erode under scrutiny.
  • The skeptic - NVIDIA's Jensen Huang said in January 2025 that "very useful" quantum computers were likely fifteen-to-twenty years out. The remark erased roughly $8 billion in quantum-stock value in a single day before he softened it weeks later. Baratz publicly called him wrong.

The pattern is not subtle: pure-play hardware vendors carrying public valuations tend to compress timelines, a chip vendor with no quantum revenue stretches them, and the underlying academic results - Willow's below-threshold memory, IBM's qLDPC code - are consistently narrower and better-defended than the press releases stacked on top of them. Read the Nature and Science papers; treat the calendar dates as positioning.

Sources & primary papers

The quantitative and attributed claims here are sourced rather than asserted, because the field moves fast enough that secondhand figures rot quickly. Primary literature:

  • Shor (1994), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer" - arXiv:quant-ph/9508027. The original algorithm.
  • Gidney & Eker� (2019), "How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits" - arXiv:1905.09749.
  • Gidney (2025), "How to factor 2048-bit RSA integers with less than a million noisy qubits" - arXiv:2505.15917.
  • Google Quantum AI (2024), "Quantum error correction below the surface code threshold" - Nature (the Willow result).
  • Bravyi, Cross, Gambetta et al. (2024), "High-threshold and low-overhead fault-tolerant quantum memory" - Nature 627, 778-782 (IBM's qLDPC codes).
  • King et al. / D-Wave (2025), "Beyond-classical computation in quantum simulation" - Science (the disputed annealing-supremacy claim).

Attributed quotes: Gambetta (IBM Quantum blog, 2025); Neven (Google Quantum AI, Dec 2024); Kulkarni (Rigetti investor releases, 2025); Baratz (D-Wave / CNBC, 2025); Huang (NVIDIA, CES, Jan 2025). The post-quantum migration target is NIST's 2024 standardization of ML-KEM, ML-DSA, and SLH-DSA. If any single figure here ages badly, it will be a qubit count - treat those as a snapshot, not a constant.