Interactive Notes · Note 08

Quantum Error
Correction

How to protect a qubit from noise without ever measuring it — the surprising solution using entanglement and the stabilizer formalism.

Repetition Code Stabilizer Groups Syndrome Extraction

Contents

Section 01

Classical Error Correction

Whenever we send information through a channel — be it fiber optic cable, radio, or the internet — noise can flip bits. Error correction codes add redundancy to detect and fix these errors. Before tackling the quantum case, let's understand the classical approach.

The Channel Model

We send a codeword c through a noisy channel. The receiver gets r = c ⊕ n, where n is the noise vector. Each bit nᵢ = 1 (error) with probability p and nᵢ = 0 (no error) with probability 1−p.

c \to [Channel] \to r = c \oplus n

The Repetition Code — The Simplest Code

The simplest idea: repeat each bit multiple times. To transmit message bit m = 0, send the codeword c = (000). To transmit m = 1, send c = (111).

At the receiver, apply a majority rule: whatever value appears most often among the three received bits is the decoded message.

Received r Decoded Correct? Probability 0000 ✓ (1-p)³ 0010 ✓ (1-p)²p 0100 ✓ (1-p)²p 0111 ✗ (1-p)p² 1000 ✓ (1 error corrected!) (1-p)²p 1011 ✗ (1-p)p² 1101 ✗ (1-p)p² 1111 ✗ (3 errors) p³

Received r	Decoded	Correct?	Probability
000	0	✓	(1−p)³
001	0	✓	(1−p)²p
010	0	✓	(1−p)²p
011	1	✗	(1−p)p²
100	0	✓ (1 error corrected!)	(1−p)²p
101	1	✗	(1−p)p²
110	1	✗	(1−p)p²
111	1	✗ (3 errors)	p³

P err with code: = 3p²(1-p) + p³ \approx 3p² (for small p) P err without: = p Improvement when: 3p² < p \Leftrightarrow p < 1/3 \to The code always helps if p < 1/2!

Code Notation [n, k, d]

A code that encodes k information bits into n physical bits and can correct up to t = ⌊(d−1)/2⌋ errors is denoted [n, k, d]. The repetition code is a [3, 1, 3] code: n=3 bits, k=1 info bit, minimum distance d=3 (corrects t=1 error).

Rate R c = k/n (repetition code: R c = 1/3) Low rate is the cost of protection — 3 physical bits for 1 logical bit

Classical repetition code — error probability comparison. Drag slider to change channel error rate p.

Channel error rate p = 0.10

Ex 1.1Error probability with the repetition code

The channel error probability is p = 0.1. What is the decoding error probability with the [3,1,3] repetition code? (Use P_err = 3p²(1−p) + p³.)

P_err ≈

3 × (0.1)² × (0.9) + (0.1)³ = 3 × 0.01 × 0.9 + 0.001 = 0.027 + 0.001 = 0.028.

Ex 1.2When does the code help?

For what values of p does the repetition code actually reduce error probability? (Compare 3p² < p.)

p <

3p² < p → 3p < 1 → p < 1/3.

Section 02

Three Challenges for Quantum Error Correction

Naively, we might try to apply classical error correction to qubits. But there are three fundamental obstacles that make this impossible without new ideas.

The challenge: quantum information is fragile in ways that classical information is not. Three quantum-specific obstacles must be overcome.

Challenge 1 — A Continuum of Errors

Classical channel 0 \to 0 with prob. 1-p 0 \to 1 with prob. p (only 1 type of error: bit-flip) Quantum channel |ψ⟩ = α|0⟩ + β|1⟩ \to |ψ̃⟩ = α|0⟩ + βe iΔ |1⟩ (continuous parameter Δ — infinitely many errors)

Surprisingly, this is NOT a real obstacle. Quantum error correction works by discretizing errors. When we perform syndrome measurement (Section 5), the continuous error collapses into one of a discrete set of Pauli errors (I, X, Y, Z). We only need to correct those!

Challenge 2 — No-Cloning Theorem

Classical (easy) b \to bbb (copy a bit 3 times) [3,1] repetition code ✓ Quantum (impossible) |ψ⟩ \to |ψ⟩|ψ⟩|ψ⟩ FORBIDDEN! No-Cloning Theorem ✗

No-Cloning Theorem: There is no unitary operation U such that U|ψ⟩|0⟩ = |ψ⟩|ψ⟩ for all states |ψ⟩. It is fundamentally impossible to copy an unknown quantum state. So the classical "just repeat it" strategy cannot be directly applied.

The quantum solution: instead of copying, we use entanglement. The quantum repetition code does not clone |ψ⟩ — it creates a specific entangled 3-qubit state that encodes the same information in a distributed way.

Challenge 3 — Measurement Collapses the State

Classical decoder Reads r = c \oplus n directly \to decides which error occurred Quantum decoder If we measure |ψ̃⟩ \to state collapses! We lose α and β forever.

The quantum solution: We never measure the data qubits directly. Instead, we perform syndrome measurement using ancilla qubits. This extracts information about the error without revealing anything about the actual data (α and β).

Ex 2.1Why can't we copy a qubit?

Suppose we could clone: U|ψ⟩|0⟩ = |ψ⟩|ψ⟩. Apply U to |+⟩|0⟩ and expand using superposition. Does the result equal |+⟩|+⟩? (Hint: expand |+⟩ = (|0⟩+|1⟩)/√2 and see what linearity gives.)

By linearity, U|+⟩|0⟩ = (U|0⟩|0⟩ + U|1⟩|0⟩)/√2 = (|00⟩ + |11⟩)/√2. But |+⟩|+⟩ = (|00⟩ + |01⟩ + |10⟩ + |11⟩)/2. These are different — the "cloner" gives an entangled state, not a product state. Contradiction!

Section 03

The Quantum Repetition Code

We want to protect the qubit |φ⟩ = α|0⟩ + β|1⟩. We cannot copy it, but we can encode it into an entangled 3-qubit state.

Encoding

Use two CNOT gates (with |φ⟩ as control) to create the codeword:

|φ⟩

─────

|0⟩

⊕

─────

|0⟩

⊕

─────

Input: |φ⟩|0⟩|0⟩ = (α|0⟩ + β|1⟩)|0⟩|0⟩ After CNOT₁: α|000⟩ + β|110⟩ After CNOT₂: |Ψ⟩ = α|000⟩ + β|111⟩ (encoded codeword) Note: |Ψ⟩ \neq |φ⟩|φ⟩|φ⟩ — this is NOT copying! It is an entangled state that encodes α and β in a distributed way.

Effect of Errors

Suppose the channel applies a Pauli X gate (bit-flip) to one of the qubits. The state becomes:

Error State after error Ancilla result I (none) α|000⟩ + β|111⟩ |00⟩ syndrome (0,0) X₀ α|100⟩ + β|011⟩ |11⟩ syndrome (1,1) X₁ α|010⟩ + β|101⟩ |11⟩ \to X₁ X₂ α|001⟩ + β|110⟩ |10⟩ syndrome (1,0)

Decoding — Without Measuring Data!

Instead of measuring |Ψ⟩ directly, we introduce two ancilla qubits and measure them. This gives us the syndrome — information about which error occurred — without revealing α or β.

data

Q. Ch.

→ |Ψ̃⟩

|0⟩ (anc)

⊕

s₁

|0⟩ (anc)

⊕

s₂

Key insight: measuring the ancilla qubits gives information about the error (which qubit was flipped) but reveals nothing about α and β. The data qubit |Ψ̃⟩ is unchanged by this measurement!

Quantum repetition code — select an error to see the syndrome and correction.

Error:

Ex 3.1Codeword verification

The encoded state is |Ψ⟩ = α|000⟩ + β|111⟩. Apply Z₀Z₁ (Pauli Z on qubits 0 and 1) to |Ψ⟩. What do you get?

Z₀|0⟩ = |0⟩, Z₀|1⟩ = −|1⟩. Z₀Z₁(α|000⟩+β|111⟩) = α·(+1)(+1)|000⟩ + β·(−1)(−1)|111⟩ = α|000⟩+β|111⟩ = |Ψ⟩. So Z₀Z₁ is a stabilizer of |Ψ⟩!

Ex 3.2Syndrome after error X₁

After an X₁ error, the state becomes α|010⟩ + β|101⟩. What is the measurement outcome (s₁, s₂) of the ancilla circuit above? The ancilla measures Z₁Z₀ and Z₂Z₁.

s₁ = s₂ =

g₁ = Z₁Z₀ anticommutes with X₁ (since X and Z anticommute on qubit 1, and I and Z commute on qubit 0). So syndrome s₁ = 1. Similarly g₂ = Z₂Z₁ anticommutes with X₁ (qubit 1 factor). So s₂ = 1. Both ancillas = 1 → error is X₁.

Section 04

Stabilizer Formalism

The stabilizer formalism provides a powerful, systematic language for quantum error correcting codes. It answers the question: what operators leave the codewords unchanged?

Group Theory Reminder

Group (G, ·)

A set G with a binary operation "·" satisfying:

Closure g₁ \cdot g₂ \in G for all g₁, g₂ \in G Associativity (g₁ \cdot g₂) \cdot g₃ = g₁ \cdot (g₂ \cdot g₃) Identity \exists e \in G such that e \cdot g = g \cdot e = g for all g Inverse For each g \in G, \exists g⁻¹ \in G such that g \cdot g⁻¹ = e

If also g₁ · g₂ = g₂ · g₁ for all g₁, g₂, the group is abelian.

The Pauli Group 𝒢ₙ

The Pauli group on n qubits consists of all tensor products of Pauli matrices {I, X, Y, Z} across n qubits, with overall phases ±1 or ±i.

𝒢₁ (1 qubit): {\pmI, \pmiI, \pmX, \pmiX, \pmY, \pmiY, \pmZ, \pmiZ} 𝒢₂ (2 qubits): {\pmI₁I₀, \pmiI₁I₀, \pmI₁X₀, ..., \pmiY₁Z₀, ...} NOT abelian: XZ = iY \neq ZX = -iY. The Pauli matrices do not always commute!

Commutation rule for Paulis: Two Pauli operators either commute (AB = BA) or anticommute (AB = −BA). On a single qubit: X and Z anticommute (XZ = −ZX), while X and X commute. On multiple qubits, two Pauli strings commute iff they anticommute on an even number of qubit positions.

The Stabilizer Set S(C)

Stabilizer Set

Given a quantum error correcting code C (a set of quantum states called codewords), the stabilizer set is:

S(C) = { M \in 𝒢ₙ : M|ψ⟩ = |ψ⟩ for all |ψ⟩ \in C }

S(C) is the set of all Pauli operators that leave every codeword unchanged.

S(C) is an Abelian Group

Proof:

Closure S₁, S₂ \in S(C) \to S₁S₂|ψ⟩ = S₁|ψ⟩ = |ψ⟩ \to S₁S₂ \in S(C) ✓ Identity I|ψ⟩ = |ψ⟩ \to I \in S(C) ✓ Inverse S \in S(C) \to S⁻¹|ψ⟩ = S⁻¹(S|ψ⟩) = e|ψ⟩ = |ψ⟩ \to S⁻¹ \in S(C) ✓ Abelian S₁S₂|ψ⟩ = S₁|ψ⟩ = |ψ⟩ and S₂S₁|ψ⟩ = S₂|ψ⟩ = |ψ⟩ \to same result \to S₁S₂ = S₂S₁ ✓

Generator Set G

Generator Set

Instead of listing all elements of S(C), we can specify a small set of generators G = {g₁, g₂, ..., gₘ} such that every element of S(C) can be written as a product of generators:

S(C) = { g₁ α₁ g₂ α₂ ... gₘ αₘ | αᵢ \in {0,1} }

If |G| = M generators → |S(C)| = 2^M stabilizers (much more compact!).

Example: Quantum Repetition Code

The code C = {α|000⟩ + β|111⟩} has the following stabilizer set and generators:

S(C) = {I, Z₁Z₀, Z₂Z₀, Z₂Z₁} (4 elements = 2² \to need 2 generators) Generators: G = {g₁, g₂} = {Z₁Z₀, Z₂Z₁} Verify g₁: Z₁Z₀(α|000⟩+β|111⟩) = α(+1)(+1)|000⟩ + β(-1)(-1)|111⟩ = α|000⟩+β|111⟩ ✓ Matrix form: The generator matrix G (rows = generators, columns = qubits): I Z Z Z Z I rows: g₁, g₂ columns: q₂, q₁, q₀

Explore which Pauli operators stabilize the encoded state α|000⟩ + β|111⟩.

Test operator:

Ex 4.1Is X₀X₁X₂ a stabilizer?

Apply X₀X₁X₂ to the codeword |Ψ⟩ = α|000⟩ + β|111⟩. Does it stabilize |Ψ⟩? (Recall X|0⟩ = |1⟩ and X|1⟩ = |0⟩.)

X₀X₁X₂(α|000⟩+β|111⟩) = α|111⟩+β|000⟩ = β|000⟩+α|111⟩. This is NOT the same as |Ψ⟩ = α|000⟩+β|111⟩ (unless α=β). So X₀X₁X₂ is NOT a stabilizer of this code.

Section 05

Syndrome Extraction

The generators of the stabilizer code tell us exactly what to measure. The key insight: measuring a generator either confirms the state is in the code space (eigenvalue +1) or reveals that an error occurred (eigenvalue −1), without disturbing the quantum information.

Commuting vs Anticommuting with Errors

Suppose the channel introduces a Pauli error E on the codeword |ψ⟩ ∈ C. The corrupted state is |ψ̃⟩ = E|ψ⟩. Now we apply a generator gᵢ:

If gᵢE = Egᵢ (commute): gᵢE|ψ⟩ = Egᵢ|ψ⟩ = E|ψ⟩ = |ψ̃⟩ \to eigenvalue +1 \to syndrome bit sᵢ = 0 If gᵢE = -Egᵢ (anticommute): gᵢE|ψ⟩ = -Egᵢ|ψ⟩ = -E|ψ⟩ = -|ψ̃⟩ \to eigenvalue -1 \to syndrome bit sᵢ = 1

Different errors give different syndromes. This is how we identify which error occurred: by checking which generators anticommute with it. The syndrome S = (s₁, s₂, ..., sₘ) uniquely identifies the error (for a good code).

The Ancilla Circuit for Syndrome Measurement

We cannot just apply gᵢ and read the eigenvalue — that would collapse |ψ̃⟩. Instead, we use an ancilla qubit and controlled-gᵢ to extract the eigenvalue into the ancilla:

|ψ̃⟩

gᵢ

|ψ̃⟩ (unchanged)

|0⟩

sᵢ ∈ {0,1}

Let's trace the ancilla through this circuit step by step:

|ψ₀⟩ = |0⟩ \otimes |ψ̃⟩ After H on ancilla: |ψ₁⟩ = |+⟩ \otimes |ψ̃⟩ = (|0⟩ + |1⟩)/\sqrt2 \otimes |ψ̃⟩ After controlled-gᵢ: |ψ₂⟩ = (|0⟩|ψ̃⟩ + |1⟩gᵢ|ψ̃⟩)/\sqrt2 = (|0⟩|ψ̃⟩ \pm |1⟩|ψ̃⟩)/\sqrt2 = |\pm⟩ \otimes |ψ̃⟩ After H on ancilla: |ψ₃⟩ = |"0" or "1"⟩ \otimes |ψ̃⟩ (ancilla tells us eigenvalue of gᵢ) Measure ancilla: Get sᵢ = 0 if gᵢE commutes (no error signature for gᵢ) or sᵢ = 1 if anticommutes (error detected!) Key fact: |ψ̃⟩ is UNCHANGED throughout this process. The data qubit is unperturbed.

Full Syndrome Table for the Repetition Code

Error E Syndrome (s₂,s₁) Correction I (0, 0) None needed ✓ X₀ (0, 1) Apply X₀ X₁ (1, 1) Apply X₁ X₂ (1, 0) Apply X₂ Z₀ = Z₁ = Z₂ (0, 0) Ambiguous with I — cannot correct Z errors! (need Shor/surface code)

Limitation: The quantum repetition code can only correct X (bit-flip) errors, not Z (phase-flip) errors. Z errors produce syndrome (0,0) — indistinguishable from no error! A full code like the Shor [[9,1,3]] code combines bit-flip and phase-flip repetition codes to handle both.

Syndrome Extraction Map S_E

The full syndrome extraction circuit performs the mapping:

S E (|0⟩ \otimes E|ψ⟩) = |S E ⟩ \otimes E|ψ⟩ The ancilla contains the syndrome — the data is unchanged

Example: S_E(|00⟩ ⊗ X₀|ψ⟩) = |01⟩ ⊗ X₀|ψ⟩ (syndrome 01, apply X₀ to correct)

Syndrome extraction — trace the ancilla state for each possible error.

Error applied:

Ex 5.1Syndrome computation

Using generators g₁ = Z₁Z₀ and g₂ = Z₂Z₁, compute the syndrome (s₂, s₁) for error E = X₀ (bit-flip on qubit 0). Does X₀ commute or anticommute with each generator?

s₁ = s₂ =

g₁ = Z₁Z₀: Z and X anticommute on qubit 0 → g₁E = −Eg₁ → s₁ = 1. g₂ = Z₂Z₁: X₀ only acts on qubit 0; neither Z₂ nor Z₁ overlaps with X₀ → g₂E = Eg₂ → s₂ = 0. Syndrome = (0,1).

Ex 5.2Why measuring ancillas doesn't disturb data?

After the syndrome circuit, the state is |S_E⟩ ⊗ E|ψ⟩ (product state). When we measure the ancilla and get syndrome s, what happens to the data part E|ψ⟩?

Since the final state is a PRODUCT state |S_E⟩ ⊗ E|ψ⟩, measuring the ancilla (first factor) does not affect the data register (second factor). They are no longer entangled. The data qubit remains exactly E|ψ⟩, which we can then correct by applying E⁻¹.

Quantum ErrorCorrection

Classical Error Correction

The Repetition Code — The Simplest Code

Three Challenges for Quantum Error Correction

Challenge 1 — A Continuum of Errors

Challenge 2 — No-Cloning Theorem

Challenge 3 — Measurement Collapses the State

The Quantum Repetition Code

Encoding

Effect of Errors

Decoding — Without Measuring Data!

Stabilizer Formalism

Group Theory Reminder

The Pauli Group 𝒢ₙ

The Stabilizer Set S(C)

Generator Set G

Example: Quantum Repetition Code

Syndrome Extraction

Commuting vs Anticommuting with Errors

The Ancilla Circuit for Syndrome Measurement

Full Syndrome Table for the Repetition Code

Quantum Error
Correction