Simple Algorithm
Quantum Computing · Rydberg State · 30 min

CSS Codes & the Steane Code

Quantum codes from pairs of classical codes.

Classical coding theory spent half a century building excellent codes. In 1996 Calderbank, Shor and Steane showed how to reuse them: a pair of nested classical codes yields a quantum code, with one code fixing bit flips and the other fixing phase flips. The construction gives the Steane code, the surface code, and today's best quantum LDPC codes.

What you’ll learn

  • Recall classical linear codes, parity-check matrices, dual codes and the Hamming code.
  • State and prove the CSS construction from C2⊥⊆C1C_2^\perp\subseteq C_1, including k=k1+k2−nk = k_1+k_2-n and d≥min⁡(d1,d2)d\ge\min(d_1,d_2).
  • Derive the Steane [[7,1,3]][[7,1,3]] code: its codewords, syndromes and transversal gates.
  • Explain the chain-complex view of CSS codes and the existence of asymptotically good CSS codes.

Classical linear codes

HHam=(000111101100111010101)H_{\text{Ham}} = \begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{pmatrix}
The [7,4,3][7,4,3] Hamming code. Column jj is jj written in binary, so the syndrome of a single flip at position jj is jj in binary.

Each row of HHamH_{\text{Ham}} has weight 4 and any two rows overlap in exactly 2 positions, so all rows are orthogonal to each other and to themselves mod 2: HHamHHamT=0H_{\text{Ham}}H_{\text{Ham}}^T = 0. Hence the dual code, the [7,3,4][7,3,4] simplex code, sits inside the Hamming code: C⊥⊆CC^\perp\subseteq C. That containment is exactly what the quantum construction needs.

The CSS construction

DerivationProof
  1. X(u) Z(v)=(−1)u⋅v Z(v) X(u)X(u)\,Z(v) = (-1)^{u\cdot v}\,Z(v)\,X(u)

    Commutation. X(u)X(u) and Z(v)Z(v) commute iff u⋅v=0u\cdot v = 0 mod 2. For u∈C2⊥⊆C1u\in C_2^\perp\subseteq C_1 and v∈C1⊥v\in C_1^\perp this holds.

  2. k=n−(n−k1)−(n−k2)=k1+k2−nk = n-(n-k_1)-(n-k_2) = k_1+k_2-n

    Dimension. There are (n−k1)+(n−k2)(n-k_1)+(n-k_2) independent generators, and each halves the dimension:

  3. ∣x+C2⊥⟩=1∣C2⊥∣∑y∈C2⊥∣x+y⟩\ket{x+C_2^\perp} = \frac{1}{\sqrt{\abs{C_2^\perp}}}\sum_{y\in C_2^\perp}\ket{x+y}

    Codewords. For x∈C1x\in C_1 the coset states below are fixed by every X(u)X(u), which permutes the terms, and by every Z(v)Z(v), since v⋅(x+y)=0v\cdot(x+y) = 0. Distinct cosets give orthogonal states, and there are ∣C1∣/∣C2⊥∣=2k1+k2−n\abs{C_1}/\abs{C_2^\perp} = 2^{k_1+k_2-n} of them:

  4. Z(v) X(ex)∣x+C2⊥⟩=(−1)v⋅ex X(ex)∣x+C2⊥⟩Z(v)\,X(e_x)\ket{x+C_2^\perp} = (-1)^{v\cdot e_x}\,X(e_x)\ket{x+C_2^\perp}

    Bit flips. An XX error X(ex)X(e_x) maps ∣x+y⟩↦∣x+y+ex⟩\ket{x+y}\mapsto\ket{x+y+e_x}. The ZZ-checks then read off H1exH_1e_x, a classical syndrome of C1C_1, so classical decoding fixes up to ⌊(d1−1)/2⌋\lfloor(d_1-1)/2\rfloor flips:

  5. H⊗n∣x+C2⊥⟩=1∣C2∣∑z∈C2(−1)x⋅z∣z⟩H^{\otimes n}\ket{x+C_2^\perp} = \frac{1}{\sqrt{\abs{C_2}}}\sum_{z\in C_2}(-1)^{x\cdot z}\ket{z}

    Phase flips. A Hadamard on every qubit exchanges the roles: the coset state of C2⊥C_2^\perp becomes a phased superposition over C2C_2, so ZZ errors become bit flips decoded with C2C_2:

  6. Distance. An undetectable error commutes with all checks: its XX part lies in (C1⊥)⊥=C1(C_1^\perp)^\perp = C_1 and its ZZ part in C2C_2. It is harmless iff it is a stabilizer, i.e. its XX part lies in C2⊥C_2^\perp and its ZZ part in C1⊥C_1^\perp. The minimum weight of a harmful one is the formula for dd. □\square

Nielsen & Chuang write the same construction with their "C2C_2" playing the role of our C2⊥C_2^\perp, i.e. C2⊂C1C_2\subset C_1 and k=k1−k2k = k_1-k_2. The two conventions describe the same codes.

The Steane code

Take C1=C2=CC_1 = C_2 = C, the [7,4,3][7,4,3] Hamming code. Since C⊥⊆CC^\perp\subseteq C, the construction gives k=4+4−7=1k = 4+4-7 = 1, with six checks: three XX-type and three ZZ-type, both read off the rows of HHamH_{\text{Ham}}.

X4X5X6X7,X2X3X6X7,X1X3X5X7,Z4Z5Z6Z7,Z2Z3Z6Z7,Z1Z3Z5Z7\begin{aligned}&X_4X_5X_6X_7,\quad X_2X_3X_6X_7,\quad X_1X_3X_5X_7,\\ &Z_4Z_5Z_6Z_7,\quad Z_2Z_3Z_6Z_7,\quad Z_1Z_3Z_5Z_7\end{aligned}
The six stabilizer generators of the Steane [[7,1,3]][[7,1,3]] code.
∣0L⟩=18∑y∈C⊥∣y⟩,∣1L⟩=18∑y∈C⊥∣y⊕1111111⟩\ket{0_L} = \frac{1}{\sqrt8}\sum_{y\in C^\perp}\ket{y},\qquad \ket{1_L} = \frac{1}{\sqrt8}\sum_{y\in C^\perp}\ket{y\oplus1111111}
∣0L⟩\ket{0_L} superposes the 8 even-weight Hamming codewords (00000000000000 and seven of weight 4); ∣1L⟩\ket{1_L} the 8 odd-weight ones (seven of weight 3, and 11111111111111).

Decoding is classical Hamming decoding, twice. The ZZ-checks give the binary position of an XX error, the XX-checks give the binary position of a ZZ error, and YjY_j lights both with the same pattern jj. The logical operators Xˉ=X⊗7\bar X = X^{\otimes7} and Zˉ=Z⊗7\bar Z = Z^{\otimes7} are equivalent, modulo stabilizers, to weight-3 operators such as X1X2X3X_1X_2X_3, because 11100001110000 is an odd-weight Hamming codeword. Hence d=3d = 3.

Check your understanding

In the Steane code, the ZZ-type checks (rows of HHamH_{\text{Ham}}, in order) report the syndrome (1,1,0)(1,1,0), and the XX-type checks report (0,0,0)(0,0,0). What happened?

  1. An XX error on qubit 3
  2. A ZZ error on qubit 6
  3. An XX error on qubit 6
  4. A YY error on qubit 6
Show the answer

C. An XX error on qubit 6

ZZ-type checks detect XX errors, and 110110 read as a binary number is 6: an XX error on qubit 6. A Y6Y_6 would also light the XX-type checks with the same pattern.

Predict before you look

The [15,11,3][15,11,3] Hamming code also contains its dual. How many logical qubits kk does the CSS code with C1=C2=[15,11,3]C_1 = C_2 = [15,11,3] encode?

Show the answer

7

k=k1+k2−n=11+11−15=7k = k_1+k_2-n = 11+11-15 = 7: the [[15,7,3]][[15,7,3]] quantum Hamming code. In general the [2r−1, 2r−1−r, 3][2^r-1,\,2^r-1-r,\,3] Hamming codes give [[2r−1, 2r−1−2r, 3]][[2^r-1,\,2^r-1-2r,\,3]] CSS codes.

Good CSS codes, and beyond

How good can CSS codes be? Picking nested codes at random, Calderbank and Shor showed that for large nn there exist CSS codes correcting arbitrary errors on tt qubits whose rate satisfies (as stated in Nielsen & Chuang)

kn  ≥  1−2 h(2tn),h(x)=−xlog⁡2x−(1−x)log⁡2(1−x)\frac kn\;\ge\;1-2\,h\Big(\frac{2t}{n}\Big),\qquad h(x) = -x\log_2x-(1-x)\log_2(1-x)
A quantum Gilbert–Varshamov-type bound: positive rate together with linear distance. "Good quantum error-correcting codes exist."

Fault tolerance also wants LDPC codes, whose checks have bounded weight and act on few qubits. Topological CSS codes such as the surface code have constant-weight checks, but rate k/n→0k/n\to0 and distance only O(n)\order{\sqrt n}. Tillich and Zémor's hypergraph product (2009) achieved constant rate with d=Θ(n)d = \Theta(\sqrt n). In 2021–22 Panteleev and Kalachev constructed asymptotically good quantum LDPC codes, with kk and dd both linear in nn, soon followed by the quantum Tanner codes of Leverrier and Zémor.

Key takeaways

  • CSS: nested classical codes C2⊥⊆C1C_2^\perp\subseteq C_1 give an [[n, k1+k2−n, d]][[n,\,k_1+k_2-n,\,d]] code with ZZ-checks from C1⊥C_1^\perp, XX-checks from C2⊥C_2^\perp, and d≥min⁡(d1,d2)d\ge\min(d_1,d_2).
  • Bit flips are decoded classically with C1C_1, phase flips with C2C_2 after a Hadamard transform; the codewords are coset states ∣x+C2⊥⟩\ket{x+C_2^\perp}.
  • The Steane [[7,1,3]][[7,1,3]] code comes from the dual-containing [7,4,3][7,4,3] Hamming code: its syndromes are binary positions, and the whole Clifford group is transversal.
  • CSS codes are chain complexes (HXHZT=0H_XH_Z^T = 0). Good CSS codes exist, and good quantum LDPC codes have been known since 2021–22.

Check yourself

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

Question 1

Two classical codes C1=[n,k1]C_1 = [n,k_1] and C2=[n,k2]C_2 = [n,k_2] satisfy C2⊥⊆C1C_2^\perp\subseteq C_1. How many logical qubits does CSS(C1,C2)\mathrm{CSS}(C_1,C_2) encode?

  1. k1−k2k_1-k_2
  2. k1+k2−nk_1+k_2-n
  3. n−k1−k2n-k_1-k_2
  4. min⁡(k1,k2)\min(k_1,k_2)
Show the answer

B. k1+k2−nk_1+k_2-n

There are n−k1n-k_1 independent ZZ-type and n−k2n-k_2 independent XX-type checks, leaving n−(n−k1)−(n−k2)=k1+k2−nn-(n-k_1)-(n-k_2) = k_1+k_2-n logical qubits: the dimension of C1/C2⊥C_1/C_2^\perp.

Question 2

Why do the XX-type and ZZ-type checks of a CSS code commute?

  1. Because Paulis on different qubits always commute
  2. Because every XX-check vector lies in C1C_1 and every ZZ-check vector in C1⊥C_1^\perp, so each pair overlaps on an even number of qubits
  3. Because XX and ZZ commute on the same qubit
  4. Because the two kinds of check are measured at different times
Show the answer

B. Because every XX-check vector lies in C1C_1 and every ZZ-check vector in C1⊥C_1^\perp, so each pair overlaps on an even number of qubits

X(u)X(u) and Z(v)Z(v) commute iff u⋅v≡0(mod2)u\cdot v\equiv0\pmod 2. The hypothesis C2⊥⊆C1C_2^\perp\subseteq C_1 puts u∈C1u\in C_1, and v∈C1⊥v\in C_1^\perp, so u⋅v=0u\cdot v = 0.

Question 3

Which states make up the Steane code's ∣0L⟩\ket{0_L}?

  1. The uniform superposition of all 16 Hamming codewords
  2. Only ∣0000000⟩\ket{0000000}
  3. The uniform superposition of the 8 odd-weight Hamming codewords
  4. The uniform superposition of the 8 even-weight Hamming codewords, i.e. of the dual code C⊥C^\perp
Show the answer

D. The uniform superposition of the 8 even-weight Hamming codewords, i.e. of the dual code C⊥C^\perp

∣0L⟩=∣0+C⊥⟩\ket{0_L} = \ket{0+C^\perp} sums over C⊥C^\perp, the [7,3,4][7,3,4] simplex code, whose words are exactly the even-weight Hamming codewords. Adding 11111111111111 gives the odd-weight ones, which form ∣1L⟩\ket{1_L}.

Question 4

On the Steane code, what does the transversal gate S⊗7S^{\otimes7} do?

  1. It implements the logical TT gate
  2. It implements the logical Sˉ†\bar S^\dagger
  3. It takes the state out of the code space
  4. It implements the logical identity
Show the answer

B. It implements the logical Sˉ†\bar S^\dagger

S⊗7∣w⟩=iwt⁡(w)∣w⟩S^{\otimes7}\ket{w} = i^{\operatorname{wt}(w)}\ket{w}. Codewords in ∣0L⟩\ket{0_L} have weight 0 or 4 (phase 1), those in ∣1L⟩\ket{1_L} weight 3 or 7 (phase i3=−ii^3 = -i). So S⊗7S^{\otimes7} acts as diag(1,−i)=Sˉ†\mathrm{diag}(1,-i) = \bar S^\dagger. It also preserves the stabilizer group, because every check has weight 4.

Further reading

  • A. R. Calderbank & P. W. Shor, "Good quantum error-correcting codes exist", Physical Review A 54, 1098 (1996).
  • A. M. Steane, "Error correcting codes in quantum theory", Physical Review Letters 77, 793 (1996); and "Multiple-particle interference and quantum error correction", Proceedings of the Royal Society A 452, 2551 (1996).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §10.4 (Cambridge, 2010).
  • F. J. MacWilliams & N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland, 1977).
  • P. Panteleev & G. Kalachev, "Asymptotically good quantum and locally testable classical LDPC codes", Proceedings of STOC (2022).