Error correction: why one logical qubit needs a thousand physical ones

When people talk about quantum computers they usually quote a qubit count. A hundred qubits, a thousand qubits. The number that actually matters is hiding behind that one: how many of those qubits does it take to make one qubit you can trust?

The answer, for the leading approach, is somewhere around a thousand. Google’s own projection from its Willow chip is that a single qubit with an error rate of one in a million would take a grid of 1,457 physical qubits.¹ Older estimates for running something like Shor’s algorithm land in the range of a thousand to ten thousand per logical qubit.²

That sounds absurd. In a normal computer you don’t need a thousand transistors to store one reliable bit. This post is my attempt to explain why the overhead is so big, why surface codes remain an important approach, and what the “below threshold” result from late 2024 actually means, without overselling it.

Qubits are bad at being left alone

A classical bit in your laptop is a big, loud thing. Billions of electrons on one side of a transistor or the other. A stray cosmic ray or a bit of heat can flip one, but it’s rare, and memory chips can fix the occasional flip with simple error-correcting codes.

A qubit is the opposite. It’s a single tiny quantum system, like a superconducting circuit cooled to near absolute zero, and its state is a delicate superposition. Any interaction with the outside world (heat, stray electromagnetic fields, the wiring you use to control it) leaks a little information about that state into the environment. Once that happens the superposition starts to fall apart. This is called decoherence.

Two numbers describe how fast it happens. T1 is how long a qubit holds onto an excited |1> before relaxing to |0>. T2 is how long the phase relationship in a superposition survives. On Google’s 105-qubit Willow processor, the mean T1 is 68 microseconds and T2 (measured with a technique called CPMG) is 89 microseconds.¹ Google’s announcement describes T1 as roughly five times better than its previous generation.³

Seventy microseconds sounds like nothing, but gates on these chips take tens to hundreds of nanoseconds,¹ so you get a few hundred operations before things go bad. On top of that, every gate itself has some chance of being slightly wrong. The best many-qubit platforms have only recently reached 99.9% fidelity on two-qubit gates, which is an error rate of one in a thousand.¹ Useful algorithms need error rates closer to one in ten billion.¹

That gap, 10^-3 versus 10^-10, is the whole problem. You don’t close seven orders of magnitude by building slightly cleaner hardware. You close it with error correction.

The obvious fix doesn’t work

If I wanted to protect a classical bit, the simplest thing is to copy it. Store 0 as 000. If noise flips one, I get 010, I take a majority vote, and I’m back to 0. This is the repetition code, and it works as long as two flips don’t happen before I check.

Quantum mechanics blocks this in two ways.

First, you can’t copy an unknown quantum state. This is the no-cloning theorem, proved by Wootters and Zurek in 1982.⁴ There’s no machine that takes an arbitrary qubit a|0> + b|1> and outputs two independent copies of it. The proof is short: copying would have to be a linear operation, and a linear operation that copies |0> and |1> correctly will produce an entangled mess, not two copies, when you feed it a superposition.

Second, you can’t just look. Measuring a qubit to check whether it got flipped collapses the superposition. The act of checking destroys the thing you’re protecting.

Early on, these two facts looked like a serious obstacle to protecting qubits at all. Then in 1995 Peter Shor published a scheme that encodes one qubit into nine and can recover from an error on any one of them.⁵ Google’s Willow announcement points out that getting error correction to actually improve as you scale up had been an open challenge ever since.³

The trick: ask about relationships, not values

Here’s the idea that makes it work, and honestly it’s one of my favorite ideas in all of quantum computing.

You don’t copy the state. You spread it out. Instead of copying a|0> + b|1> into three separate qubits, you entangle three qubits into a|000> + b|111>. That’s not three copies. It’s one logical qubit whose information lives in the correlations between three physical ones. No-cloning isn’t violated because you never had two independent copies of anything.

Now suppose noise flips the middle qubit. The state becomes a|010> + b|101>. To find the error, you don’t measure any qubit directly. You measure parities: “do qubits 1 and 2 agree?” and “do qubits 2 and 3 agree?”

Look at what those questions return. In a|010> + b|101>, qubits 1 and 2 disagree in both branches. Qubits 2 and 3 also disagree in both branches. So the answer is “disagree, disagree” with certainty, no matter what a and b are. The measurement tells you where the error is and nothing at all about the data. The superposition survives. You flip qubit 2 back and you’re done.

The pattern of check results is called the syndrome, and in practice you measure it by entangling each pair of data qubits with an extra helper qubit (a measure qubit) and measuring only the helper. This is the basic shape of every code in this post: data qubits hold the information, measure qubits keep asking parity questions, and a classical computer called a decoder reads the syndromes and figures out the most likely error.

Bit flips are only half of it

The repetition code above catches bit flips (X errors, |0> to |1>). But qubits also suffer phase flips (Z errors), which turn |0> + |1> into |0> - |1>. A classical bit has no phase, so classical codes never had to deal with this.

The fix is to also run checks in a rotated basis, where phase flips look like bit flips. Shor’s nine-qubit code is basically a repetition code for bit flips nested inside a repetition code for phase flips.⁵

There’s one more worry. Real errors are continuous. A qubit doesn’t flip cleanly, it drifts by some small random angle. It turns out this doesn’t matter: measuring the syndrome forces the error to “pick” a discrete outcome, either no error or a specific flip. Aharonov and Ben-Or give a short proof that correcting bit flips and phase flips is enough to handle general errors.⁶

This is the part that made quantum error correction feel less like magic to me. The measurement that could have destroyed you is the same thing that turns analog noise into digital errors you can fix.

The surface code

Shor’s code proved the idea was possible. The code most hardware teams actually use today is the surface code, which grew out of Kitaev’s work on topological codes in the late 1990s.⁷⁸

Picture a checkerboard. Data qubits sit on the corners. Measure qubits sit in the middle of each square, and each one checks the parity of the four data qubits around it. Half the squares check for bit flips, half check for phase flips, alternating like the colors on the board.

The reason people like it so much comes down to three properties.

1. Every check is local. Each measure qubit only talks to its four neighbors. That matters a lot on a flat chip where qubits can only be wired to the ones next to them.
2. It tolerates high error rates. Fowler and colleagues’ 2012 review puts the surface code’s per-operation error tolerance as high as about 1%, which is far more forgiving than older schemes.²
3. It scales by just getting bigger. The logical information is stored in the pattern across the whole grid. To corrupt it, errors have to form a chain stretching from one edge to the other. A bigger grid means longer chains, which are less likely.

The code distance, d, is the minimum weight of a nontrivial logical operator. A distance-d code can correct up to floor((d - 1) / 2) arbitrary errors, though actual failure rates depend on the noise and decoder. In the layout Google uses, a distance-d code takes d^2 data qubits plus d^2 - 1 measure qubits, so 2d^2 - 1 physical qubits total.¹

d = 3   ->    17 qubits
d = 5   ->    49 qubits
d = 7   ->    97 qubits   (Willow used 101, counting 4 leakage-removal helpers)
d = 27  ->  1457 qubits

That quadratic growth is where the “thousand” comes from. You don’t need a thousand because each qubit is terrible. You need it because protection grows with the distance and cost grows with the distance squared.

The threshold theorem

So here’s the catch with adding more qubits. Every new qubit is also a new place for errors to happen. If your hardware is noisy enough, a bigger code just gives noise more places to start, and the logical qubit gets worse, not better.

The threshold theorem says there’s a crossover point. If the physical error rate p is below some threshold p_thr, then making the code bigger suppresses logical errors, and you can drive them as low as you want. Aharonov and Ben-Or proved a version of this in the 1990s for error rates below a constant threshold,⁶ and Dennis, Kitaev, Landahl and Preskill showed the surface code has one too, framing it as a phase transition.⁸

For the surface code, the Willow paper writes the approximate relationship like this:¹

logical error  ε_d  ∝  (p / p_thr) ^ ((d + 1) / 2)

The ratio p / p_thr gets raised to a power that grows with distance. If the ratio is below 1, a bigger exponent means a smaller number, fast. If it’s above 1, a bigger exponent makes things blow up.

The cleanest way to measure this is a single number, Λ (lambda): how much the logical error rate drops each time you increase the distance by 2.¹

Λ = ε_d / ε_(d+2)  ≈  p_thr / p

If Λ > 1, you’re below threshold, and every step up in size divides your error rate by Λ. If Λ < 1, you’re above threshold and error correction is making things worse. For years, that was the honest state of affairs.

Here’s a quick sketch in Python, with the Willow numbers plugged in:

eps_7 = 1.43e-3   # measured logical error per cycle at d = 7
lam = 2.14        # measured suppression factor

for d in range(7, 29, 4):
    eps = eps_7 / lam ** ((d - 7) / 2)
    print(d, 2 * d * d - 1, f"{eps:.1e}")
# 7   97  1.4e-03
# 11 241  3.1e-04
# 15 449  6.8e-05
# 19 721  1.5e-05
# 23 1057 3.3e-06
# 27 1457 7.1e-07

This is a naive extrapolation and assumes nothing else goes wrong at scale, which is exactly what you can’t assume. But it shows the shape: each factor of about 2 costs one more step in distance, which is tens of qubits at small sizes and a couple hundred near d = 27.

What Willow actually showed

In December 2024, Google Quantum AI published “Quantum error correction below the surface code threshold” in Nature.¹ Here’s what’s in it, as plainly as I can put it.

• They ran surface code memories at distance 3, 5 and 7 on the 105-qubit Willow chip.
• Each step up in distance cut the logical error rate by Λ = 2.14 ± 0.02 with their neural network decoder.¹ Google’s blog phrases this as halving the error rate at each step.³
• The distance-7 code, using 101 qubits, had a logical error of 0.143% per cycle of error correction.¹
• The distance-7 logical qubit lasted 291 microseconds on average, about 2.4 times longer than the best physical qubit in it.¹
• With a real-time decoder keeping up with the chip, the distance-5 code stayed below threshold for up to a million cycles, with decoder latency averaging 63 microseconds against a 1.1 microsecond cycle.¹

The important comparison is with Google’s previous attempt. In 2022 to 2023, on an older chip, their distance-5 code only barely beat distance-3: a logical error per cycle of 2.914% versus 3.028%.⁹ That’s Λ of about 1.04. Technically better, practically a tie. Going from “barely improves” to “halves at every step” is the difference between error correction being a theory and being an engineering roadmap.

What it didn’t show

This is the part I think gets lost in headlines, so I want to be careful.

It’s a memory, not a computer. The experiment stored one logical qubit and kept it alive. It didn’t run logical gates between logical qubits. The paper says directly that more challenges will show up when doing logical computation instead of storage.¹

10^-3 is still bad. A logical error of about one in a thousand per cycle is roughly where good physical gates already are. The win is the trend, not the number. Useful algorithms want something like 10^-10 or lower.¹

The extrapolation has a floor. Google also ran repetition codes (which only protect against one kind of flip) up to distance 29. They saw clean exponential suppression for a while, then it leveled off at around 10^-10, caused by rare bursts of correlated errors that hit many qubits at once, roughly once an hour.¹ Threshold results require assumptions about noise, which can allow some local correlations. Rare large bursts can violate those assumptions and limit the extrapolation.

The random circuit sampling claim is a separate thing. Google’s announcement also said Willow ran a benchmark in under five minutes that would take a top supercomputer 10 septillion years.³ That’s a different experiment, and it isn’t about error correction. Google’s own post says it expects classical methods to keep improving on that benchmark.³ I’d keep the two results in different boxes.

Λ around 2 is just barely enough. Because Λ ≈ p_thr / p, a Λ of 2 means the hardware is only about twice as good as the threshold. That’s why the overhead is so large. The paper points out the flip side: halve the physical error rate and the distance-27 code improves by about four orders of magnitude.¹ That’s the red line in the chart above. Below threshold, better hardware can substantially reduce the coding overhead.

So why “a thousand”?

Putting it together, the overhead comes from three things stacked on top of each other.

1. You can’t copy, so you have to spread one qubit’s information across many and keep checking relationships, which needs extra measure qubits on top of the data qubits.
2. Today’s hardware is only modestly below threshold, so each step up in distance only buys a factor of about 2.
3. Cost grows with d^2 while protection grows with d, so getting from 10^-3 to 10^-6 or 10^-12 takes a big grid.

Fowler’s 2012 review estimates that with physical error rates around 10^-3, a logical qubit needs 10^3 to 10^4 physical qubits to get logical error rates down to 10^-14 or 10^-15,² and in its factoring example, about 14,500 physical qubits per logical qubit.² Willow’s own extrapolation is 1,457 for 10^-6.¹ “A thousand” is shorthand for that order of magnitude, and the real number depends heavily on how good the hardware gets.

The same logic is why estimates for breaking RSA are so large. In 2019, Gidney and Ekerå estimated that factoring a 2048-bit RSA number would take about 20 million noisy qubits running for 8 hours.¹⁰ In May 2025, Gidney revised that to fewer than a million noisy qubits running for under a week, assuming a 0.1% gate error rate, using cleverer arithmetic and better ways to pack idle logical qubits.¹¹ Error correction is most of that budget. I went through what those numbers mean for RSA in the Shor post, and every one of those estimates assumes error-corrected logical qubits underneath.

What I keep thinking about

The overhead numbers are going down from both directions. Hardware gets cleaner, which raises Λ. And theory gets smarter: Gidney’s drop from 20 million to under a million came almost entirely from better algorithms and encodings, not better chips.¹⁰¹¹ The Willow paper also expects overheads to fall with better codes and decoders.¹

The decoder part is what I find most interesting as someone who mostly writes software. Willow’s best decoder was a neural network fine-tuned on data from the actual processor.¹ And the real-time decoder has to process a fresh round of syndromes every 1.1 microseconds, forever, without falling behind.¹ That’s a classical computing problem sitting right in the middle of a quantum one.

I like that progress can come from both the device and the software trying to make sense of its errors. It makes me wonder how much the resource estimates could change as those pieces improve together.

Willow’s measured improvement as the code grows is exciting, but I’d want to see how well that trend holds as systems get larger and errors interact in new ways. The overhead is still a serious part of the problem. Understanding where it can fall seems like one of the most interesting ways to get closer to a useful machine.

Sources