Quantum bits (qubits) are fragile: interactions with their environment cause errors. Quantum error correction (QEC) uses redundancy and clever encoding to detect and fix these errors without measuring and collapsing the quantum state. Below we cover the main ideas and early codes developed before 2020.

Types of Quantum Errors

Qubits suffer two primary kinds of errors:

  • Bit-flip (X error): |0⟩ ↔ |1⟩
  • Phase-flip (Z error): |+⟩ ↔ |−⟩, where |±⟩ = (|0⟩ ± |1⟩)/√2

General errors can be expressed as combinations of X, Z, and Y = iXZ.

The Three-Qubit Code

One of the earliest QEC schemes encodes a logical qubit |ψ⟩ = α|0⟩ + β|1⟩ into three physical qubits:

$$ |0_L⟩ = |000⟩, \quad |1_L⟩ = |111⟩. $$

To detect bit-flips, parity checks between qubit pairs are measured using ancillary qubits. A single X error on any one qubit produces a unique syndrome pattern, allowing correction by applying X to the affected qubit. This code corrects only bit-flips, not phase-flips [4].

Shor’s Nine-Qubit Code

Peter Shor combined bit- and phase-flip protection into a nine-qubit code. First, encode against phase errors using a three-qubit repetition of the Hadamard basis, then protect each of those with a three-qubit bit-flip code. The logical states are:

$$ |0_L⟩ = \frac{1}{2\sqrt{2}}(|000⟩ + |111⟩)^{\otimes 3}, \quad |1_L⟩ = \frac{1}{2\sqrt{2}}(|000⟩ - |111⟩)^{\otimes 3}. $$

Shor’s code corrects any single-qubit error (X, Z, or Y) by cascading bit- and phase-syndrome measurements [3].

Stabilizer Formalism

Stabilizer codes generalize Shor’s idea using groups of Pauli operators that leave logical states invariant. An [[n,k]] stabilizer code encodes k logical qubits into n physical qubits. The [[5,1]] code is the smallest single-error-correcting code, requiring only five qubits [2]. Stabilizer generators {gi} satisfy gi|ψ_L⟩ = +|ψ_L⟩.

CSS Codes

Calderbank–Shor–Steane (CSS) codes build on classical linear codes. They correct X and Z errors separately using two classical codes C1 and C2 with C2 ⊂ C1. Many prominent codes, including Steane’s [[7,1]] code and the surface code, fit into the CSS framework [5].

Surface Codes and Topological Protection

Surface codes arrange qubits on a 2D lattice with nearest-neighbor interactions. Error detection uses local parity checks around plaquettes and vertices. Surface codes offer high thresholds (≈1%) and require only local gates, making them practical for architectures like superconducting qubits [7].

Threshold Theorem and Concatenation

The quantum threshold theorem states that if physical error rates are below a threshold (typically 10⁻⁴ to 10⁻²), arbitrarily long quantum computation is possible using concatenated codes and fault-tolerant gates [9]. Concatenation stacks codes recursively to drive logical error rates down exponentially.

References

[1] Nielsen, M. A., & Chuang, I. L. (2000). Quantum Computation and Quantum Information. Cambridge University Press.

[2] Gottesman, D. (1997). Stabilizer Codes and Quantum Error Correction. arXiv:quant-ph/9705052.

[3] Shor, P. W. (1995). Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52(4), R2493.

[4] Laflamme, R., Miquel, C., Paz, J.-P., & Zurek, W. H. (1996). Perfect quantum error correcting code. Physical Review Letters, 77(1), 198.

[5] Steane, A. M. (1996). Error Correcting Codes in Quantum Theory. Physical Review Letters, 77(5), 793.

[6] Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012). Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86(3), 032324.

[7] Raussendorf, R., Harrington, J., & Goyal, K. (2007). Topological fault-tolerance in cluster state quantum computation. New Journal of Physics, 9(6), 199.

[8] Aharonov, D., & Ben-Or, M. (1997). Fault-tolerant quantum computation with constant error. arXiv:quant-ph/9611025.

[9] Terhal, B. M. (2015). Quantum error correction for quantum memories. Reviews of Modern Physics, 87(2), 307.