← Quantum Information & Computing
🛡️
Topic 9 of 12

Quantum Error Correction

Decoherence — unwanted interaction with the environment — is the central challenge for quantum computing. Quantum error correction (QEC) encodes one logical qubit into many physical qubits, allowing errors to be detected and corrected without ever measuring (and collapsing) the logical qubit. Shor's 9-qubit code (1995) proved in principle that fault-tolerant quantum computation is possible.

Key Concepts

Decoherence and Errors
Quantum errors come in two types: bit-flip errors (XX: ∣0⟩↔∣1⟩|0\rangle\leftrightarrow|1\rangle) and phase-flip errors (ZZ: changes sign of ∣1⟩|1\rangle). A general single-qubit error is a combination of these. Environmental noise causes decoherence — the quantum state loses its superposition into a probabilistic mixture.
3-Qubit Bit-Flip Code
Encodes ∣0⟩L=∣000⟩|0\rangle_L = |000\rangle and ∣1⟩L=∣111⟩|1\rangle_L = |111\rangle. A bit-flip on any one qubit is detected by measuring the parities Z1Z2Z_1Z_2 and Z2Z3Z_2Z_3 (syndrome measurements) without learning the logical state. The syndrome identifies which qubit flipped, enabling correction.
[[n, k, d]] Notation
A quantum error correcting code [[n,k,d]][[n,k,d]] uses nn physical qubits to encode kk logical qubits with distance dd. Distance dd codes can correct t=⌊(d−1)/2⌋t = \lfloor(d-1)/2\rfloor arbitrary errors and detect up to d−1d-1 errors. The rate is k/nk/n (information density).
Shor Code [[9,1,3]]
The first quantum error correcting code (Shor 1995). Uses 9 physical qubits to encode 1 logical qubit with distance 3. Concatenates the 3-qubit bit-flip code and the 3-qubit phase-flip code to correct arbitrary single-qubit errors. Proved fault-tolerant quantum computation is possible in principle.
Stabilizer Formalism
Most practical QEC codes are stabilizer codes, described by an Abelian group of Pauli operators (the stabilizer) that fix the code space. Syndrome measurement projects onto the +1+1 eigenspace of each stabilizer without measuring the logical qubit. The Steane [[7,1,3]] and surface codes are key examples.
Fault-Tolerance Threshold
If the physical error rate pp is below a threshold pth≈0.1%−1%p_{th} \approx 0.1\%-1\% (depending on the code and architecture), concatenated error correction allows the logical error rate to be reduced arbitrarily. The threshold theorem proves fault-tolerant quantum computation is possible with realistic hardware.

Key Equations

Code Parameters
[[n,k,d]]: encodes k logical qubits in n physical, corrects t=⌊(d−1)/2⌋ errors[[n, k, d]]: \text{ encodes } k \text{ logical qubits in } n \text{ physical, corrects } t = \lfloor(d-1)/2\rfloor \text{ errors}
The three key parameters of any quantum error correcting code.
Syndrome Measurement
g1=Z1Z2,g2=Z2Z3(3-qubit code)g_1 = Z_1 Z_2, \quad g_2 = Z_2 Z_3 \quad (\text{3-qubit code})
Syndrome operators for the 3-qubit bit-flip code; measure parities without collapsing logical qubit.
Logical Encoding (Bit-Flip Code)
∣0⟩L=∣000⟩,∣1⟩L=∣111⟩|0\rangle_L = |000\rangle, \quad |1\rangle_L = |111\rangle
Majority-vote encoding protects against single bit flips.
Fault Tolerance Threshold
p<pth≈10−2  ⟹  arbitrarily low logical error rate possiblep < p_{th} \approx 10^{-2} \implies \text{arbitrarily low logical error rate possible}
Below the threshold, more code concatenation always reduces error, enabling scalable quantum computing.
Worked Example

3-Qubit Bit-Flip Code: Detection and Correction

Problem

A logical qubit ∣ψ⟩L=α∣000⟩+β∣111⟩|\psi\rangle_L = \alpha|000\rangle + \beta|111\rangle suffers a bit-flip on the second qubit. Show how syndrome measurement detects and corrects the error.

Solution

After error on qubit 2: state becomes α∣010⟩+β∣101⟩\alpha|010\rangle + \beta|101\rangle.

Measure syndrome operator Z1Z2Z_1Z_2 (parity of qubits 1 and 2):

Z1Z2(α∣010⟩+β∣101⟩)=α(−∣010⟩)+β(−∣101⟩)  ⟹  eigenvalue=−1Z_1Z_2(\alpha|010\rangle + \beta|101\rangle) = \alpha(-|010\rangle) + \beta(-|101\rangle) \implies \text{eigenvalue} = -1

Measure syndrome Z2Z3Z_2Z_3:

Z2Z3(α∣010⟩+β∣101⟩)=α(−∣010⟩)+β(−∣101⟩)  ⟹  eigenvalue=−1Z_2Z_3(\alpha|010\rangle + \beta|101\rangle) = \alpha(-|010\rangle) + \beta(-|101\rangle) \implies \text{eigenvalue} = -1

Syndrome table: (Z1Z2,Z2Z3)=(−1,−1)(Z_1Z_2, Z_2Z_3) = (-1,-1) → error on qubit 2. Apply X2X_2 to correct.

X2(α∣010⟩+β∣101⟩)=α∣000⟩+β∣111⟩=∣ψ⟩L✓X_2(\alpha|010\rangle+\beta|101\rangle) = \alpha|000\rangle+\beta|111\rangle = |\psi\rangle_L \checkmark
Answer Syndrome (-1,-1) identifies error on qubit 2; applying X₂ restores the logical state.
Practice

Exercises

6 problems
1 of 6

A [[3,1,3]][[3,1,3]] code has distance d=3d=3. It corrects tt errors where d=2t+1d = 2t+1. What is tt?

errors
2 of 6

Shor's code [[9,1,3]][[9,1,3]] uses how many physical qubits per logical qubit?

qubits
3 of 6

The [[5,1,3]][[5,1,3]] code is the smallest code correcting 1 arbitrary error. How many physical qubits does it use?

Unlock Exercise 3

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →
4 of 6

A code with distance dd can DETECT (not correct) up to d−1d-1 errors. For the Steane [[7,1,3]][[7,1,3]] code with d=3d=3, how many errors can it detect?

Unlock Exercise 4

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →
5 of 6

The fault-tolerance threshold error rate is approximately pth≈1%p_{th} \approx 1\%. Express this as a decimal.

Unlock Exercise 5

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →
6 of 6

How many logical qubits (kk) does the Steane [[7,1,3]][[7,1,3]] code encode?

Unlock Exercise 6

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

Key Takeaways

  • Quantum errors are combinations of bit-flips (XX) and phase-flips (ZZ); correcting both requires a full QEC code.
  • 3-qubit bit-flip code: ∣0⟩L=∣000⟩,∣1⟩L=∣111⟩|0\rangle_L=|000\rangle, |1\rangle_L=|111\rangle; syndromes Z1Z2,Z2Z3Z_1Z_2, Z_2Z_3 identify the error without measuring the logical qubit.
  • [[n,k,d]][[n,k,d]] code encodes kk logical qubits in nn physical qubits and corrects t=⌊(d−1)/2⌋t=\lfloor(d-1)/2\rfloor errors.
  • The fault-tolerance threshold theorem: if p<pth≈1%p < p_{th}\approx1\%, arbitrarily reliable computation is achievable.
  • Surface codes with pth≈1%p_{th}\approx1\% are the leading practical QEC approach for near-term hardware.
← Previous Shor's Factoring Algorithm