Quantum Error Correction

Quantum Error Correction#

Why quantum errors are fundamentally different from classical errors. The error correction conditions, the threshold theorem, and fault tolerance.

Quantum error correction (QEC) is the theory and practice of protecting quantum information from noise. Without it, quantum computation at scale is impossible. NISQ devices operate without error correction, which limits them to shallow circuits. Fault-tolerant quantum computing requires QEC, and understanding its principles is essential for understanding the resource overhead of algorithms like Shor’s.

Why Quantum Errors Are Different#

Classical error correction is straightforward: copy the bit, check for flips, correct by majority vote. Quantum error correction faces three fundamental obstacles:

No-cloning theorem: An unknown quantum state \(|\psi\rangle\) cannot be copied. This rules out the classical strategy of redundant copies.

Continuous errors: Classical bits flip discretely (0 to 1). Qubits can experience continuous rotations of their amplitudes, so the error space is infinite-dimensional.

Measurement destroys information: Reading a qubit collapses its state. You cannot directly inspect a quantum state to check for errors without destroying the computation.

How QEC Overcomes These Obstacles

QEC encodes one logical qubit into multiple physical qubits using entanglement (not copying). Errors are detected by measuring syndromes (parity checks on ancilla qubits) that reveal error information without collapsing the encoded state. The continuous error space is handled by the fact that any error can be decomposed into discrete Pauli errors (\(I\), \(X\), \(Y\), \(Z\)), and correcting these discrete errors suffices.

The Error Model#

The most common error model decomposes arbitrary single-qubit errors into Pauli operators:

Bit flip (\(X\)): \(|0\rangle \leftrightarrow |1\rangle\)
Phase flip (\(Z\)): \(|0\rangle + |1\rangle \to |0\rangle - |1\rangle\)
Bit-phase flip (\(Y = iXZ\)): both simultaneously

Any single-qubit error channel \(\mathcal{E}\) can be written as:

\[\mathcal{E}(\rho) = (1-p)\rho + p_x X\rho X + p_y Y\rho Y + p_z Z\rho Z\]

where \(p = p_x + p_y + p_z\) is the total error probability. The depolarizing channel has \(p_x = p_y = p_z = p/3\).

This discretization is the key insight: if a code can correct all single-qubit Pauli errors, it automatically corrects all single-qubit errors (including continuous rotations), because any error is a linear combination of Paulis.

Quantum Error Correcting Codes#

A quantum error correcting code encodes \(k\) logical qubits into \(n\) physical qubits, written as \([[n, k, d]]\), where \(d\) is the code distance: the minimum weight of an undetectable error (the number of physical qubits that must be corrupted simultaneously to cause a logical error).

A code with distance \(d\) can:

Detect up to \(d-1\) errors
Correct up to \(\lfloor (d-1)/2 \rfloor\) errors

Code	\([[n, k, d]]\)	Corrects
3-qubit bit flip	\([[3, 1, 1]]\)	1 bit flip
3-qubit phase flip	\([[3, 1, 1]]\)	1 phase flip
Shor code	\([[9, 1, 3]]\)	Any single-qubit error
Steane code	\([[7, 1, 3]]\)	Any single-qubit error
5-qubit code	\([[5, 1, 3]]\)	Any single-qubit error (optimal)
Surface code	\([[O(d^2), 1, d]]\)	\(\lfloor (d-1)/2 \rfloor\) errors

The Knill-Laflamme Conditions#

A code with codespace \(\mathcal{C}\) corrects a set of errors \(\{E_a\}\) if and only if:

\[\langle\psi_i|E_a^\dagger E_b|\psi_j\rangle = C_{ab}\delta_{ij}\]

for all codewords \(|\psi_i\rangle, |\psi_j\rangle\) and all error pairs \(E_a, E_b\). The matrix \(C_{ab}\) depends on the errors but not on the codewords. This condition ensures that errors do not entangle the codespace with the error syndrome, so syndrome measurement extracts error information without disturbing the encoded state.

Syndrome Measurement#

Error detection works by measuring stabilizers, operators that leave all codewords invariant. Measuring a stabilizer returns \(+1\) for no error or \(-1\) if a specific error has occurred. The pattern of stabilizer measurement outcomes (the syndrome) identifies the error without revealing the encoded information.

Logical qubit |ψ_L> ──────[error]──────[syndrome extraction]──[correction]──
                                              │
Ancilla |0>        ──────────────────[measure]──→ syndrome bits

The syndrome bits tell you which Pauli error occurred, and you apply the corresponding correction.

The Threshold Theorem#

The threshold theorem (Aharonov & Ben-Or, 1997; Knill, Laflamme & Zurek, 1998) is the foundational result of fault-tolerant quantum computing:

If the physical error rate \(p\) is below a threshold \(p_{\text{th}}\), then arbitrarily long quantum computations can be performed with arbitrarily low logical error rate, at the cost of polylogarithmic overhead in the number of physical qubits and gates.

The logical error rate decreases exponentially with the code distance:

\[p_L \approx A \left(\frac{p}{p_{\text{th}}}\right)^{\lfloor(d+1)/2\rfloor}\]

For surface codes, \(p_{\text{th}} \approx 1\%\). Current hardware error rates (\(\sim 10^{-3}\)) are approaching this threshold, which is why surface codes are the leading candidate for practical QEC.

Important

The threshold theorem guarantees that fault-tolerant quantum computing is possible in principle. The practical challenge is the overhead: encoding one logical qubit in a surface code at useful error rates requires hundreds to thousands of physical qubits. This is why breaking RSA-2048 requires millions of physical qubits despite needing only ~4,000 logical qubits.

Fault Tolerance#

It is not enough for the code to correct errors; the error correction procedure itself must not introduce more errors than it fixes. A fault-tolerant protocol ensures that a single physical error during syndrome extraction does not cause two errors in the data block.

Key techniques for fault tolerance:

Transversal gates: Apply the logical gate by applying physical gates independently to each qubit. A single failure affects only one qubit per code block.
Magic state distillation: Produce high-fidelity \(T\)-states from noisy ones. Required because the \(T\) gate is not transversal for most codes.
Concatenation: Encode a code within a code. Each level of concatenation suppresses the error rate exponentially.

Quantum Error Correction

Contents

Quantum Error Correction#

Why Quantum Errors Are Different#

The Error Model#

Quantum Error Correcting Codes#

The Knill-Laflamme Conditions#

Syndrome Measurement#

The Threshold Theorem#

Fault Tolerance#

Further Reading#