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 , including and .
- Derive the Steane 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
Each row of 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: . Hence the dual code, the simplex code, sits inside the Hamming code: . That containment is exactly what the quantum construction needs.
The CSS construction
Commutation. and commute iff mod 2. For and this holds.
Dimension. There are independent generators, and each halves the dimension:
Codewords. For the coset states below are fixed by every , which permutes the terms, and by every , since . Distinct cosets give orthogonal states, and there are of them:
Bit flips. An error maps . The -checks then read off , a classical syndrome of , so classical decoding fixes up to flips:
Phase flips. A Hadamard on every qubit exchanges the roles: the coset state of becomes a phased superposition over , so errors become bit flips decoded with :
Distance. An undetectable error commutes with all checks: its part lies in and its part in . It is harmless iff it is a stabilizer, i.e. its part lies in and its part in . The minimum weight of a harmful one is the formula for .
Nielsen & Chuang write the same construction with their "" playing the role of our , i.e. and . The two conventions describe the same codes.
The Steane code
Take , the Hamming code. Since , the construction gives , with six checks: three -type and three -type, both read off the rows of .
Decoding is classical Hamming decoding, twice. The -checks give the binary position of an error, the -checks give the binary position of a error, and lights both with the same pattern . The logical operators and are equivalent, modulo stabilizers, to weight-3 operators such as , because is an odd-weight Hamming codeword. Hence .
In the Steane code, the -type checks (rows of , in order) report the syndrome , and the -type checks report . What happened?
- An error on qubit 3
- A error on qubit 6
- An error on qubit 6
- A error on qubit 6
Show the answer
C. An error on qubit 6
-type checks detect errors, and read as a binary number is 6: an error on qubit 6. A would also light the -type checks with the same pattern.
The Hamming code also contains its dual. How many logical qubits does the CSS code with encode?
Show the answer
7
: the quantum Hamming code. In general the Hamming codes give 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 there exist CSS codes correcting arbitrary errors on qubits whose rate satisfies (as stated in Nielsen & Chuang)
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 and distance only . Tillich and Zémor's hypergraph product (2009) achieved constant rate with . In 2021–22 Panteleev and Kalachev constructed asymptotically good quantum LDPC codes, with and both linear in , soon followed by the quantum Tanner codes of Leverrier and Zémor.
Key takeaways
- CSS: nested classical codes give an code with -checks from , -checks from , and .
- Bit flips are decoded classically with , phase flips with after a Hadamard transform; the codewords are coset states .
- The Steane code comes from the dual-containing Hamming code: its syndromes are binary positions, and the whole Clifford group is transversal.
- CSS codes are chain complexes (). 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.
Two classical codes and satisfy . How many logical qubits does encode?
Show the answer
B.
There are independent -type and independent -type checks, leaving logical qubits: the dimension of .
Why do the -type and -type checks of a CSS code commute?
- Because Paulis on different qubits always commute
- Because every -check vector lies in and every -check vector in , so each pair overlaps on an even number of qubits
- Because and commute on the same qubit
- Because the two kinds of check are measured at different times
Show the answer
B. Because every -check vector lies in and every -check vector in , so each pair overlaps on an even number of qubits
and commute iff . The hypothesis puts , and , so .
Which states make up the Steane code's ?
- The uniform superposition of all 16 Hamming codewords
- Only
- The uniform superposition of the 8 odd-weight Hamming codewords
- The uniform superposition of the 8 even-weight Hamming codewords, i.e. of the dual code
Show the answer
D. The uniform superposition of the 8 even-weight Hamming codewords, i.e. of the dual code
sums over , the simplex code, whose words are exactly the even-weight Hamming codewords. Adding gives the odd-weight ones, which form .
On the Steane code, what does the transversal gate do?
- It implements the logical gate
- It implements the logical
- It takes the state out of the code space
- It implements the logical identity
Show the answer
B. It implements the logical
. Codewords in have weight 0 or 4 (phase 1), those in weight 3 or 7 (phase ). So acts as . 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).