Chapter 18: Quantum Error Correction

Part VI: Quantum Information

No-Cloning Theorem

The no-cloning theorem (Wootters & Zurek, 1982) states that it is impossible to create an identical copy of an arbitrary unknown quantum state:

This seems to make error correction impossible — classical codes work by copying bits. The key insight is that quantum error correction encodes information in entanglement, not copies. Errors are detected without measuring (and collapsing) the logical qubit.

The 3-Qubit Bit-Flip Code

The simplest quantum error correcting code maps logical states into entangled three-qubit states:

\( |\bar{0}\rangle = |000\rangle, \quad |\bar{1}\rangle = |111\rangle \)

\( |\bar{\psi}\rangle = \alpha|000\rangle + \beta|111\rangle \)

Error detection: Measure the stabilizers\(Z_1 Z_2\) and \(Z_2 Z_3\). These commute with the logical qubit but anticommute with bit-flip errors. Results reveal which qubit flipped without revealing the logical state.

Correction: Apply \(X\) to the identified qubit. Corrects any single-qubit bit flip with probability\(1 - 3p^2 + 2p^3 \approx 1 - 3p^2\) for small \(p\).

Shor's 9-Qubit Code

Peter Shor (1995) constructed the first code correcting arbitrary single-qubit errors by concatenating a 3-qubit bit-flip code with a 3-qubit phase-flip code:

\( |\bar{0}\rangle = \frac{1}{2\sqrt{2}}(|000\rangle+|111\rangle)^{\otimes 3} \)

\( |\bar{1}\rangle = \frac{1}{2\sqrt{2}}(|000\rangle-|111\rangle)^{\otimes 3} \)

Since any single-qubit error is a linear combination of \(I, X, Y, Z\)operators, correcting X errors and Z errors independently corrects all errors. This uses 9 physical qubits to protect 1 logical qubit — the [[9,1,3]] code.

Stabilizer Formalism & Surface Codes

Gottesman (1997) introduced the stabilizer formalism: a code space is defined as the +1 eigenspace of a set of Pauli operators (stabilizers). This allows efficient classical description of exponentially large quantum codes.

Surface codes (Kitaev, 1997; Fowler et al., 2012) arrange qubits on a 2D lattice with local stabilizer checks. Key properties:

Threshold: \(p_{\text{th}} \approx 1\%\) — highest known for 2D local codes
Below threshold: logical error rate \(p_L \propto \exp(-\alpha L)\) for distance-\(L\) code
Only requires nearest-neighbor interactions — physically realistic
Currently the leading platform for fault-tolerant quantum computation

Surface Code Lattice (5×5)

Surface code: data qubits (purple circles) with alternating X and Z stabilizer plaquettes. Logical operators run along paths connecting opposite boundaries.

Python: 3-Qubit Code Simulation

Simulate the 3-qubit bit-flip code with Monte Carlo trials, compare logical vs physical error rates, and show surface code distance scaling.

Python

script.py158 lines

import numpy as np
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt

np.random.seed(42)

# ── 3-qubit bit-flip code ────────────────────────────────────────────────────
# Encoding: |0> -> |000>, |1> -> |111>
# Error model: each qubit flips independently with probability p_err
# Decoding: majority vote
# Logical error: majority of 3 qubits are wrong -> at least 2 qubits flipped

def encode_3qubit(logical_bit):
    """Encode logical 0 or 1 -> 3 physical qubits."""
    return [logical_bit] * 3

def apply_bit_flip_errors(codeword, p_err):
    """Apply independent bit flip to each qubit with probability p_err."""
    return [1 - q if np.random.random() < p_err else q for q in codeword]

def decode_majority(codeword):
    """Majority vote decoding."""
    return 1 if sum(codeword) >= 2 else 0

def logical_error_rate_exact(p_err):
    """Exact probability that majority vote fails (2 or 3 qubits flipped)."""
    # P(2 errors) + P(3 errors)
    p2 = 3 * p_err**2 * (1 - p_err)
    p3 = p_err**3
    return p2 + p3

def uncoded_error_rate(p_err):
    return p_err

# ── Monte Carlo simulation ───────────────────────────────────────────────────
N_trials = 20000
p_err_range = np.linspace(0, 0.5, 100)

# Exact curves
logical_rates = [logical_error_rate_exact(p) for p in p_err_range]
uncoded_rates = list(p_err_range)

# Crossover point: 3p^2(1-p) + p^3 = p => where repetition code helps
# 3p^2 - 2p^3 = p => 3p - 2p^2 = 1 => p = 1/3 is crossover?
# Actually crossover: p_L = p when 3p^2 - 2p^3 = p => 3p - 2p^2 = 1 at p=1/2
# For p < 1/2: logical_error_rate < p (code helps)
crossover = 0.5  # at p=0.5 both are equal

# Monte Carlo at a few specific error rates
p_test_vals = [0.01, 0.05, 0.1, 0.2, 0.3, 0.4, 0.5]
print("=== 3-Qubit Bit-Flip Code Simulation ===")
print(f"N_trials = {N_trials}")
print()
print(f"{'p_err':>6} | {'Exact p_L':>10} | {'Monte Carlo p_L':>15} | {'Uncoded p':>10} | {'Gain':>8}")
print("-" * 60)

mc_results = []
for p_t in p_test_vals:
    errors = 0
    for _ in range(N_trials):
        logical = np.random.randint(0, 2)
        codeword = encode_3qubit(logical)
        noisy = apply_bit_flip_errors(codeword, p_t)
        decoded = decode_majority(noisy)
        if decoded != logical:
            errors += 1
    p_L_mc = errors / N_trials
    p_L_exact = logical_error_rate_exact(p_t)
    gain = p_t / p_L_exact if p_L_exact > 0 else float('inf')
    mc_results.append(p_L_mc)
    print(f"{p_t:6.3f} | {p_L_exact:10.5f} | {p_L_mc:15.5f} | {p_t:10.5f} | {gain:8.2f}x")

print()
print("Code helps (p_L < p) when physical error rate p < 0.5")
print("Threshold theorem: below threshold, adding more code qubits reduces p_L exponentially")

# ── Shor code summary ────────────────────────────────────────────────────────
print()
print("=== Shor 9-Qubit Code Summary ===")
print("Encodes 1 logical qubit into 9 physical qubits")
print("Corrects ANY single-qubit error (X, Y, Z, or arbitrary rotations)")
print("First quantum error correcting code (Shor 1995)")
print("Structure: 3 repetitions of 3-qubit phase-flip protection around bit-flip code")

# ── Surface code threshold ────────────────────────────────────────────────────
print()
print("=== Surface Code Threshold ===")
print("Topological surface code on L×L lattice:")
print("  Physical qubits: O(L^2)")
print("  Logical qubits: 1")
print("  Distance: d = L (corrects floor((d-1)/2) errors)")
p_threshold = 0.01  # ~1% for surface code with standard noise
print(f"  Threshold: p_th ≈ {p_threshold*100:.0f}% (one of highest known)")
print("  Below threshold: logical error rate ~ exp(-alpha*L)")

# ── Plotting ──────────────────────────────────────────────────────────────────
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
fig.patch.set_facecolor('#0a0a1a')

# Plot 1: Logical error rate vs physical error rate
ax1 = axes[0]
ax1.semilogy(p_err_range, uncoded_rates, color='#f87171', linewidth=2.5, label='Uncoded (p_L = p)')
ax1.semilogy(p_err_range, logical_rates, color='#818cf8', linewidth=2.5, label='3-qubit code (exact)')
ax1.semilogy(p_test_vals, mc_results, 'o', color='#fbbf24', markersize=7, label='Monte Carlo')
ax1.axvline(0.5, color='#34d399', linestyle='--', linewidth=1.5, alpha=0.8, label='Crossover p=0.5')
ax1.fill_between(p_err_range[:50], logical_rates[:50], uncoded_rates[:50],
                 alpha=0.12, color='#34d399', label='Region where code helps')
ax1.set_xlabel('Physical error rate p', color='white', fontsize=11)
ax1.set_ylabel('Logical error rate p_L', color='white', fontsize=11)
ax1.set_title("3-Qubit Bit-Flip Code\np_L = 3p²(1-p) + p³", color='white', fontsize=12, fontweight='bold')
ax1.legend(fontsize=8, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax1.set_facecolor('#0a0a1a')
ax1.tick_params(colors='white')
ax1.grid(True, alpha=0.2, color='#818cf8')
for sp in ax1.spines.values(): sp.set_color('#818cf8')

# Plot 2: Linear scale comparison for low error rates
ax2 = axes[1]
p_low = np.linspace(0, 0.15, 200)
ax2.plot(p_low, p_low, color='#f87171', linewidth=2.5, label='Uncoded')
ax2.plot(p_low, [logical_error_rate_exact(p) for p in p_low], color='#818cf8', linewidth=2.5, label='3-qubit code')
ax2.plot(p_low, [logical_error_rate_exact(p)**1.5 for p in p_low], color='#a5b4fc', linewidth=2, linestyle='--', label='Better code (schematic)')
ax2.set_xlabel('Physical error rate p', color='white', fontsize=11)
ax2.set_ylabel('Logical error rate', color='white', fontsize=11)
ax2.set_title("Error Rate Reduction\n(Low Error Regime)", color='white', fontsize=12, fontweight='bold')
ax2.legend(fontsize=9, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax2.set_facecolor('#0a0a1a')
ax2.tick_params(colors='white')
ax2.grid(True, alpha=0.2, color='#818cf8')
for sp in ax2.spines.values(): sp.set_color('#818cf8')

# Plot 3: Surface code logical error rate vs code distance
p_phys = 0.005  # 0.5% physical error rate (below threshold)
L_vals = np.arange(3, 20, 2)  # odd distances for surface code
# Logical error rate scales as (p/p_th)^((L+1)/2) approximately
p_th = 0.01
p_L_surface = 0.1 * (p_phys / p_th) ** ((L_vals + 1) / 2)

ax3 = axes[2]
ax3.semilogy(L_vals, p_L_surface, 'o-', color='#818cf8', linewidth=2.5, markersize=7,
             label=f'Surface code (p={p_phys*100:.1f}% < threshold)')
ax3.axhline(p_phys, color='#f87171', linestyle='--', linewidth=1.5, alpha=0.8, label=f'Physical p={p_phys*100:.1f}%')
ax3.axhline(1e-10, color='#34d399', linestyle=':', linewidth=1.5, alpha=0.8, label='Target p_L=10⁻¹⁰')
ax3.set_xlabel('Code distance L', color='white', fontsize=11)
ax3.set_ylabel('Logical error rate p_L', color='white', fontsize=11)
ax3.set_title("Surface Code Scaling\nExponential Suppression", color='white', fontsize=12, fontweight='bold')
ax3.legend(fontsize=9, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax3.set_facecolor('#0a0a1a')
ax3.tick_params(colors='white')
ax3.grid(True, alpha=0.2, color='#818cf8')
for sp in ax3.spines.values(): sp.set_color('#818cf8')

plt.tight_layout()
plt.savefig('output.png', dpi=150, bbox_inches='tight', facecolor='#0a0a1a')
plt.show()
print("\nFault tolerance: below threshold, increasing code distance exponentially suppresses errors.")

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Ch 17: Quantum Channels Ch 19: Data Compression →