Simple Algorithm
Quantum Computing · Excited State · 24 min

Quantum Error Correction Basics

Protecting information you are not allowed to look at.

Error correction looks impossible for qubits: you cannot copy them, you cannot look at them, and their errors form a continuum. In this lesson you build, gate by gate, the codes that get around all three obstacles, ending with Shor's nine-qubit code, which corrects any error on a single qubit.

What you’ll learn

  • Encode a qubit into the three-qubit bit-flip and phase-flip codes and decode their syndrome tables.
  • Extract syndromes with ancillas without disturbing the encoded superposition.
  • Derive the logical error rate 3p2−2p33p^2-2p^3 and the break-even point p=12p = \tfrac12.
  • Explain how Shor's code corrects arbitrary single-qubit errors, and why correcting XX and ZZ is enough (discretization of errors).

The bit-flip code

Encode ∣ψ⟩=α∣0⟩+β∣1⟩\ket\psi = \alpha\ket0+\beta\ket1 into three qubits with two CNOTs from the data qubit onto two fresh qubits in ∣0⟩\ket0:

α∣0⟩+β∣1⟩  ⟼  α∣000⟩+β∣111⟩=α∣0L⟩+β∣1L⟩\alpha\ket{0}+\beta\ket{1}\;\longmapsto\;\alpha\ket{000}+\beta\ket{111} = \alpha\ket{0_L}+\beta\ket{1_L}
The code space is spanned by ∣0L⟩=∣000⟩\ket{0_L} = \ket{000} and ∣1L⟩=∣111⟩\ket{1_L} = \ket{111}. Nothing is cloned: the result is entangled, not ∣ψ⟩⊗3\ket\psi^{\otimes3}.

A bit flip XjX_j moves the state out of the code space into one of three orthogonal subspaces, one per qubit. The parity operators Z1Z2Z_1Z_2 and Z2Z3Z_2Z_3 have every code state as a +1+1 eigenstate, and each single flip anticommutes with a different subset of them. Their eigenvalues form the syndrome:

ErrorState after the errorZ1Z2Z_1Z_2Z2Z3Z_2Z_3Correction
noneα∣000⟩+β∣111⟩\alpha\ket{000}+\beta\ket{111}+1+1+1+1none
X1X_1α∣100⟩+β∣011⟩\alpha\ket{100}+\beta\ket{011}−1-1+1+1X1X_1
X2X_2α∣010⟩+β∣101⟩\alpha\ket{010}+\beta\ket{101}−1-1−1-1X2X_2
X3X_3α∣001⟩+β∣110⟩\alpha\ket{001}+\beta\ket{110}+1+1−1-1X3X_3
DerivationLogical error rate
  1. pL=(32)p2(1−p)+p3=3p2−2p3p_L = \binom{3}{2}p^2(1-p)+p^3 = 3p^2-2p^3

    With independent flips of probability pp, decoding fails exactly when at least two qubits flip:

  2. 3p2−2p3<p  ⟺  p (2p−1)(p−1)>0  ⟺  p<123p^2-2p^3<p\iff p\,(2p-1)(p-1)>0\iff p<\tfrac12

    The code helps iff pL<pp_L<p. For 0<p<10<p<1 the factor p−1p-1 is negative, so this requires 2p−1<02p-1<0:

  3. For small pp, pL≈3p2p_L\approx3p^2: errors are suppressed quadratically. At p=10−3p = 10^{-3}, pL≈3×10−6p_L\approx3\times10^{-6}.

Predict before you look

For the three-qubit bit-flip code with independent flips at p=5%p = 5\%, what is the logical error rate, in %?

Show the answer

0.725 %

pL=3p2−2p3=3(0.0025)−2(0.000125)=0.00725p_L = 3p^2-2p^3 = 3(0.0025)-2(0.000125) = 0.00725, i.e. 0.725%: about seven times better than the unencoded 5%.

Measuring the syndrome without measuring the data

Measuring Z1Z2Z_1Z_2 is a two-qubit measurement. In a circuit you copy the parity onto an ancilla with two CNOTs and measure the ancilla instead. Why doesn't that collapse the encoded superposition?

DerivationThe ancillas factor out
  1. (α∣010⟩+β∣101⟩)∣00⟩a1a2\big(\alpha\ket{010}+\beta\ket{101}\big)\ket{00}_{a_1a_2}

    Suppose X2X_2 occurred. Add ancillas a1a_1 (for Z1Z2Z_1Z_2) and a2a_2 (for Z2Z3Z_2Z_3), both in ∣0⟩\ket0:

  2. ⟼  α∣010⟩∣11⟩+β∣101⟩∣11⟩=(α∣010⟩+β∣101⟩)⊗∣11⟩\longmapsto\;\alpha\ket{010}\ket{11}+\beta\ket{101}\ket{11} = \big(\alpha\ket{010}+\beta\ket{101}\big)\otimes\ket{11}

    CNOTs from qubits 1 and 2 onto a1a_1, and from qubits 2 and 3 onto a2a_2, write the parities into the ancillas. Both branches have the same parities:

  3. The ancillas end up in a product state with the data. Measuring them gives 1111 with certainty and reveals nothing about α\alpha or β\beta. Applying X2X_2 finishes the job.

Phase flips: the same code in the Hadamard basis

A ZZ error commutes with Z1Z2Z_1Z_2 and Z2Z3Z_2Z_3, so the bit-flip code is blind to it. But HZH=XHZH = X: in the basis ∣±⟩\ket\pm a phase flip is a bit flip, since Z∣±⟩=∣∓⟩Z\ket\pm = \ket\mp. So encode in that basis:

∣0L⟩=∣+++⟩,∣1L⟩=∣−−−⟩,checks X1X2, X2X3\ket{0_L} = \ket{{+}{+}{+}},\qquad \ket{1_L} = \ket{{-}{-}{-}},\qquad\text{checks } X_1X_2,\ X_2X_3
Encoding circuit: the two CNOTs of the bit-flip code, followed by a Hadamard on every qubit.

Every statement about the bit-flip code transfers by conjugating with H⊗3H^{\otimes3}. The syndromes X1X2X_1X_2 and X2X3X_2X_3 locate a single ZZ error, which is undone by applying ZjZ_j. Measuring X1X2X_1X_2 uses the same ancilla circuit sandwiched between Hadamards on the data qubits.

Check your understanding

In the phase-flip code, a ZZ error hits qubit 3. What do the checks X1X2X_1X_2 and X2X3X_2X_3 report?

  1. +1, +1+1,\ +1
  2. −1, +1-1,\ +1
  3. +1, −1+1,\ -1
  4. −1, −1-1,\ -1
Show the answer

C. +1, −1+1,\ -1

Z3Z_3 anticommutes with X2X3X_2X_3 (they meet on qubit 3, ZZ against XX) and commutes with X1X2X_1X_2 (no overlap). It is the same pattern as X3X_3 in the bit-flip code.

Shor's nine-qubit code and the discretization of errors

Concatenate the two codes: protect each qubit of the phase-flip code with its own bit-flip code (Shor 1995).

∣0L⟩=122(∣000⟩+∣111⟩)⊗3,∣1L⟩=122(∣000⟩−∣111⟩)⊗3\ket{0_L} = \frac{1}{2\sqrt2}\big(\ket{000}+\ket{111}\big)^{\otimes3},\qquad \ket{1_L} = \frac{1}{2\sqrt2}\big(\ket{000}-\ket{111}\big)^{\otimes3}
ChecksOperatorsWhat they detect
Inner (bit-flip)Z1Z2, Z2Z3, Z4Z5, Z5Z6, Z7Z8, Z8Z9Z_1Z_2,\ Z_2Z_3,\ Z_4Z_5,\ Z_5Z_6,\ Z_7Z_8,\ Z_8Z_9one XX error in any block of three
Outer (phase-flip)X1X2X3X4X5X6,  X4X5X6X7X8X9X_1X_2X_3X_4X_5X_6,\ \ X_4X_5X_6X_7X_8X_9one sign flip among the three blocks
Eight checks give 28=2562^8 = 256 syndromes. A ZZ on any qubit of a block flips that block's sign in ∣000⟩±∣111⟩\ket{000}\pm\ket{111}, and Y=iXZY = iXZ triggers both kinds of check.
Check your understanding

A ZZ error hits qubit 5 (in the middle block) of Shor's code. Which checks report −1-1?

  1. Z4Z5Z_4Z_5 and Z5Z6Z_5Z_6
  2. Only X4X5X6X7X8X9X_4X_5X_6X_7X_8X_9
  3. No check: Z5Z_5 is undetectable
  4. Both outer checks, X1⋯X6X_1\cdots X_6 and X4⋯X9X_4\cdots X_9
Show the answer

D. Both outer checks, X1⋯X6X_1\cdots X_6 and X4⋯X9X_4\cdots X_9

Z5Z_5 anticommutes with every check that contains X5X_5, i.e. both outer checks, and commutes with all the ZZ-type checks. The pattern (−1,−1)(-1,-1) on the outer checks points to the middle block, and applying ZZ to any of its qubits (Z4Z_4, Z5Z_5 or Z6Z_6) undoes the error.

Notice the last point: Z4Z_4, Z5Z_5 and Z6Z_6 act identically on the code space, because Z4Z5Z_4Z_5 and Z5Z6Z_5Z_6 are checks and act trivially on code states. The decoder need not know which of them happened. Codes in which distinct errors have the same effect are called degenerate, a purely quantum phenomenon.

DerivationWhy correcting X, Y and Z corrects everything
  1. E=e0 I+e1Xj+e2Yj+e3ZjE = e_0\,\id+e_1X_j+e_2Y_j+e_3Z_j

    Any operator acting on qubit jj is a linear combination of Paulis:

  2. E∣ψL⟩=e0∣ψL⟩+e1Xj∣ψL⟩+e2Yj∣ψL⟩+e3Zj∣ψL⟩E\ket{\psi_L} = e_0\ket{\psi_L}+e_1X_j\ket{\psi_L}+e_2Y_j\ket{\psi_L}+e_3Z_j\ket{\psi_L}

    Acting on a code state, it produces a superposition of four standard error branches:

  3. E∣ψL⟩ → syndrome of Zj  Zj∣ψL⟩ → apply Zj  ∣ψL⟩E\ket{\psi_L}\ \xrightarrow{\ \text{syndrome of }Z_j\ }\ Z_j\ket{\psi_L}\ \xrightarrow{\ \text{apply }Z_j\ }\ \ket{\psi_L}

    In Shor's code the four branches have different syndromes, so they lie in mutually orthogonal subspaces. Measuring the syndrome projects onto one branch, say Zj∣ψL⟩Z_j\ket{\psi_L} with probability ∣e3∣2/∑i∣ei∣2\abs{e_3}^2/\sum_i\abs{e_i}^2, and the correction then restores ∣ψL⟩\ket{\psi_L} exactly:

  4. By linearity the same holds for every Kraus operator of any single-qubit noise channel and for coherent rotations: e−iθX1/2e^{-i\theta X_1/2} becomes "no error" with probability cos⁡2θ2\cos^2\tfrac\theta2 and a full X1X_1 with probability sin⁡2θ2\sin^2\tfrac\theta2. A code that corrects a discrete set of errors corrects every linear combination of them.

Key takeaways

  • The bit-flip code α∣000⟩+β∣111⟩\alpha\ket{000}+\beta\ket{111} corrects one XX error using the parities Z1Z2Z_1Z_2 and Z2Z3Z_2Z_3; its logical error rate 3p2−2p33p^2-2p^3 beats pp whenever p<12p<\tfrac12.
  • Syndromes are extracted with CNOTs onto ancillas. Every code state has the same parities, so the ancillas factor out and the superposition survives.
  • Conjugating by Hadamards gives the phase-flip code for ZZ errors; Shor's code concatenates the two and corrects an arbitrary single-qubit error.
  • Syndrome measurement discretizes errors: correcting I\id, XX, YY, ZZ on each qubit corrects every linear combination, including small coherent rotations.
  • Quantum codes can be degenerate: different errors may act identically on the code space.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In the bit-flip code the syndrome is Z1Z2=+1Z_1Z_2 = +1, Z2Z3=−1Z_2Z_3 = -1. Which correction do you apply?

  1. X1X_1
  2. X2X_2
  3. X3X_3
  4. None
Show the answer

C. X3X_3

Only qubit 3 belongs to Z2Z3Z_2Z_3 but not to Z1Z2Z_1Z_2, so a flip there changes exactly the second parity.

Question 2

Why can't the phase-flip code {∣+++⟩,∣−−−⟩}\{\ket{{+}{+}{+}},\ket{{-}{-}{-}}\} correct a single XX error?

  1. Because XX errors are too rare to matter
  2. Because XjX_j commutes with both checks, yet acts on the code space as a logical ZZ (it flips the sign of ∣−−−⟩\ket{{-}{-}{-}})
  3. Because XX errors take the state out of the qubits' Hilbert space
  4. Because measuring X1X2X_1X_2 collapses the encoded state
Show the answer

B. Because XjX_j commutes with both checks, yet acts on the code space as a logical ZZ (it flips the sign of ∣−−−⟩\ket{{-}{-}{-}})

X∣±⟩=±∣±⟩X\ket\pm = \pm\ket\pm, so Xj∣+++⟩=∣+++⟩X_j\ket{{+}{+}{+}} = \ket{{+}{+}{+}} while Xj∣−−−⟩=−∣−−−⟩X_j\ket{{-}{-}{-}} = -\ket{{-}{-}{-}}: an undetectable logical phase flip. The phase-flip code just swaps which kind of error is invisible.

Question 3

A small coherent error e−iθX1/2e^{-i\theta X_1/2} acts on a qubit encoded in the bit-flip code, and then the syndrome is measured. What happens?

  1. The code fails, because only discrete errors can be corrected
  2. A residual rotation of order θ2\theta^2 is left over
  3. With probability cos⁡2θ2\cos^2\tfrac\theta2 the syndrome is trivial and the state is restored exactly; otherwise X1X_1 is detected and corrected
  4. The syndrome measurement amplifies the error into a logical flip
Show the answer

C. With probability cos⁡2θ2\cos^2\tfrac\theta2 the syndrome is trivial and the state is restored exactly; otherwise X1X_1 is detected and corrected

e−iθX1/2=cos⁡θ2 I−isin⁡θ2 X1e^{-i\theta X_1/2} = \cos\tfrac\theta2\,\id-i\sin\tfrac\theta2\,X_1. The two branches have different syndromes, so the measurement collapses onto one of them, and both outcomes are fully recoverable.

Question 4

Which of these multi-qubit errors does Shor's code correct?

  1. X1X2X_1X_2
  2. Z1Z4Z_1Z_4
  3. X1X4X_1X_4
  4. Z1Z4Z7Z_1Z_4Z_7
Show the answer

C. X1X4X_1X_4

X1X_1 and X4X_4 sit in different blocks, and each inner bit-flip code fixes its own single flip independently.

Go deeper

Further reading

  • P. W. Shor, "Scheme for reducing decoherence in quantum computer memory", Physical Review A 52, R2493 (1995).
  • A. M. Steane, "Error correcting codes in quantum theory", Physical Review Letters 77, 793 (1996).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §10.1–10.3 (Cambridge, 10th anniv. ed., 2010).
  • S. J. Devitt, W. J. Munro & K. Nemoto, "Quantum error correction for beginners", Reports on Progress in Physics 76, 076001 (2013).