Why Quantum Computers Need Error Correction
The Fragility Problem
A classical computer bit is robust — it is either 0 or 1, and thermal noise typically must cross a large energy barrier to flip it. A qubit, by contrast, exists in a delicate superposition that can be disrupted by any interaction with the environment. This process is called decoherence.
Decoherence manifests in two timescales: T1 (energy relaxation, where |1⟩ spontaneously decays to |0⟩) and T2 (dephasing, where the phase relationship between |0⟩ and |1⟩ is randomised). Current superconducting qubits have T1 and T2 times on the order of microseconds to milliseconds — far shorter than the time required for useful algorithms.
Gate operations also introduce errors. Even the best two-qubit gates today have error rates of around 0.1–1% per operation. For algorithms requiring millions of gates (like Shor's algorithm at cryptographically relevant scales), errors accumulate disastrously without correction.
Why Classical Error Correction Fails
No-Cloning Theorem
Classical redundancy copies bits: 0 → 000, then majority vote corrects errors. Quantum mechanics forbids copying an unknown quantum state, so direct redundancy is impossible.
Measurement Collapse
Checking a qubit for errors by measuring it destroys the superposition. QEC instead uses ancilla qubits to measure error syndromes — properties that reveal error type without revealing (collapsing) the logical state.
Continuous Error Space
Classical errors are discrete (a bit flips or doesn't). Quantum errors are continuous rotations. The key insight: any error on a qubit is a linear combination of Pauli operators {I, X, Y, Z} — so correcting these discrete cases covers all possibilities.
Two Error Types
Quantum errors come in two flavours: bit-flip errors (X: swaps |0⟩ and |1⟩) and phase-flip errors (Z: sends |+⟩ to |−⟩). A complete QEC code must handle both simultaneously.
Shor's 9-Qubit Code
Syndrome Measurement
The central technique in QEC is measuring stabilisers — multi-qubit Pauli operators that commute with the code space but anticommute with errors. Measuring these stabilisers projects the error onto a discrete set of outcomes (the error syndrome) without disturbing the logical information encoded in the code space.
For example, in the three-qubit bit-flip code (|0⟩ → |000⟩, |1⟩ → |111⟩), measuring the parity of qubits 1&2 and qubits 2&3 reveals which (if any) qubit flipped without revealing whether the logical qubit is 0 or 1. The error is then corrected by applying the appropriate Pauli gate.
Notable QEC Codes
The Surface Code
The Fault-Tolerance Threshold Theorem
A Critical Milestone
The threshold theorem states: if physical gate error rates fall below a code-specific threshold, then by encoding information in more physical qubits, logical error rates can be suppressed arbitrarily close to zero. Below the threshold, more redundancy helps; above it, more qubits make things worse.
Surface code threshold: Approximately 1% per gate — achievable with current hardware. IBM's and Google's best processors reach ~99.5–99.9% two-qubit gate fidelity, putting them near but not yet comfortably below the threshold when all overhead is included.
The overhead cost: Current estimates suggest approximately 1,000 physical qubits per logical qubit at achievable error rates. A fault-tolerant attack on RSA-2048 via Shor's algorithm requires roughly 4,000 logical qubits → ~4 million physical qubits. Today's processors have ~1,000–2,000 physical qubits total.