Quantum Error Correction and Post Quantum Cryptography: The Missing Piece Before Q-Day

Why Error Correction Is the Whole Ball Game

Running Shor's algorithm on a real RSA key takes billions of logical gate operations. If even one in a thousand operations corrupts the state, the answer is garbage. So before a Cryptographically Relevant Quantum Computer exists, quantum error correction has to scale from tabletop demonstrations to the thousands-of-logical-qubits regime. This is the real bottleneck on the quantum threat timeline.

What Makes Quantum Errors Different

Classical error correction (Hamming codes, Reed-Solomon, Turbo codes) works because bits have two states and errors are bit flips. You replicate the bit, majority vote, done.

Quantum errors are harder because:

1. No cloning. Quantum mechanics forbids copying an unknown quantum state (the no-cloning theorem). You cannot just replicate a qubit three times.
2. Continuous errors. Qubits can drift by small angles, not just flip. Error correction must round partial errors back to canonical values.
3. Measurement destroys information. Direct measurement to check for errors would collapse the superposition. Error detection must be indirect via ancilla qubits.

Quantum codes solve these three problems by encoding one logical qubit into a larger entangled system and detecting errors via syndrome measurements that do not reveal the encoded information.

The Surface Code in Plain Terms

The surface code is the most practical quantum error correction code today. It arranges physical qubits on a 2D grid. A logical qubit is encoded across a d-by-d patch for some odd integer d (the code distance).

The key properties:

• Threshold behavior. If physical gate errors are below roughly 1 percent, logical error rate drops exponentially with d.
• Local checks. Every error syndrome is measured by a small group of neighboring physical qubits. This is friendly to the 2D chip layouts superconducting platforms use.
• Cost. Distance d requires approximately 2d^2 physical qubits per logical qubit, plus ancilla qubits for syndrome extraction.

To run Shor on RSA-2048 you need logical error rate around 10^-10, which requires d somewhere around 25, which means around 1,250 physical qubits per logical qubit, which means millions of physical qubits total. That is where the 20-million-physical-qubit estimate comes from.

Google Willow in December 2024

Willow (105 physical qubits) demonstrated the surface code at distances 3, 5, and 7. As distance increased, logical error rate halved at each step. This is called below-threshold scaling. It was the first convincing demonstration that increasing the code distance on real hardware actually improves the logical qubit, rather than the opposite (above threshold hardware gets worse as you add qubits, because more qubits means more errors faster than the code can correct).

Willow did not produce a cryptographically useful logical qubit. It produced evidence that the path to one is not blocked by physics, only by engineering and scale.

Other Codes in the Race

• Color codes. Transversal non-Clifford gates possible, but harder to fabricate.
• LDPC codes. Higher code rate (more logical per physical), but require non-local connectivity.
• Topological codes (e.g. Majorana). Native fault tolerance if the physical substrate cooperates; Microsoft has pursued this for years.
• Concatenated codes. Classical hierarchical construction; less efficient than surface code for 2D hardware.

Magic State Distillation

The surface code gives you cheap Clifford gates (Hadamard, CNOT, S). To run Shor you need non-Clifford gates like the T gate. Those require magic states produced by a distillation protocol that consumes many physical qubits per magic state. In most resource estimates, the magic state factories consume more physical qubits than the Shor circuit itself.

This is why counting qubits does not translate directly to breaking RSA. Even with 20 million qubits, most are in distillation, not in the cryptographic circuit.

What Matters for Your PQC Migration

Follow the error-correction research, not the qubit-count press releases. The milestones that would compress the CRQC timeline:

• Surface code at d=15 or higher with sustained low logical error rate.
• Real-time classical decoders that keep up with quantum gate speeds.
• Magic state distillation with sub-10x physical qubit overhead.
• LDPC codes implementable on near-term chips.

None of these are close to ready. But progress has been steadier than headline capacity numbers suggest.

Frequently Asked Questions

Why can't we just add more qubits to fix errors?

Because errors happen during the extra qubit operations too. Without the code being below threshold, adding qubits makes things worse. Below-threshold operation (Willow December 2024) is a necessary prerequisite before scaling helps.

Is the surface code the only option?

No. Color codes, LDPC codes, concatenated codes, and topological codes all have research communities. Surface code dominates in practice because of its locality and relatively high threshold.

What is magic state distillation?

A protocol that produces special ancilla states called magic states. These states are consumed to execute non-Clifford gates (like the T gate) fault-tolerantly. Distillation costs many physical qubits per produced magic state.

How much of Shor's resource cost is error correction?

Most of it. Under reasonable surface code assumptions for RSA-2048, roughly 20 million physical qubits are required, and the majority are dedicated to magic state distillation and code overhead rather than Shor's circuit itself.

Sources

1. Google: Making Quantum Error Correction Work
2. Willow Nature paper
3. Fowler et al. (2012). Surface codes
4. Gidney & Ekera (2021)

Related Articles

• Logical Qubits vs Physical Qubits
• Google Willow
• CRQC Explained
• Shor's Algorithm
• What Is a Qubit?