Notes on quantum error correction · Part 2.5 · beyond Roffe's guide · previous: Part 2 · next: Part 3
Tanner graphs
A parity-check matrix says which checks touch which qubits. Drawn as a graph, with a circle for every qubit and a square for every check, the same information becomes a picture: an error marks circles, every square that meets the marked circles an odd number of times lights up, and a decoder is a rule for reading the lit squares back. Part 3 writes each CSS code as two such matrices and part 4 runs belief propagation on their graphs, so this part introduces the picture first, on codes already met: the three-qubit code, the classical Hamming code, the \([[4,2,2]]\) and Shor codes, and, a little ahead of part 3, the Steane code. The figures are at the end, followed by problems.
From a matrix to a graph
Take any binary matrix \(H\) with \(m\) rows and \(n\) columns. Its Tanner graph has one node per column, drawn as a circle and called a bit or qubit node, and one node per row, drawn as a square and called a check node, with an edge between check \(i\) and qubit \(j\) exactly where \(H_{ij} = 1\). No edge ever joins two circles or two squares: the graph is bipartite. The three-qubit code of part 1 has
\[ H_{\text{rep}} = \begin{pmatrix} 1&1&0 \\ 0&1&1 \end{pmatrix}, \]so its graph has three circles and two squares: circle 1 is joined to square 1, circle 3 to square 2, and circle 2 to both. Drawn in a line it is a path, circle, square, circle, square, circle. The Hamming matrix of part 3,
\[ 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}, \]gives seven circles and three squares, each square joined to four circles, and circle \(j\) joined to as many squares as there are 1s in the binary form of \(j\): one square for circles 1, 2, 4, two for 3, 5, 6, three for circle 7.
Nothing is added and nothing is lost in the drawing. A row of \(H\) is the neighbourhood of a square, the set of circles it touches; a column is the neighbourhood of a circle. The number of edges at a node is its degree, the weight of that row or column. What the picture adds is the thing a table hides: how the neighbourhoods overlap, which is what every argument about syndromes and decoders turns on (figure 1). In figure A at the end, hovering a node shows its neighbourhood.
Syndromes light the squares
A pattern of flips \(e\) marks some circles. Each square counts the marked circles among its neighbours: an even count leaves it satisfied, an odd count lights it. Row by row that is the parity check \(s_i = \sum_j H_{ij} e_j\) mod 2, so the lit squares are the syndrome \(s = He\). On the repetition graph, marking circle 2 lights both squares, marking circle 1 lights the first only, and marking circles 1 and 2 together lights only the second, because square 1 meets the marks twice. On the Hamming graph, marking circle 5 lights squares 1 and 3, the binary digits of 5 (figure 2).
A set of circles that lights nothing is a set every square meets an even number of times. That is exactly a vector in \(\ker H\): a codeword of the classical code. Such a set is invisible to the checks, and the smallest non-empty invisible set has size \(d\), the classical distance. The Hamming graph makes \(d = 3\) visible without computation: one circle always lights something, since no column is zero; two circles light nothing only if they have the same neighbourhood, and no two columns are equal; and the three circles 1, 2, 3 are invisible, since every square meets them twice or not at all.
Decoding is a puzzle on the graph
The decoder sees only the lit squares and has to guess the marks. Its task has a graphical statement:
That is \(H\hat e = s\) with \(|\hat e|\) as small as possible, minimum-weight decoding, and three things about it can be read off the picture.
Lookup. When every circle has a different neighbourhood, a lit pattern that equals one circle's neighbourhood names that circle, and nothing lighter fits. On the Hamming graph every single flip is decoded this way: squares 1 and 3 lit means circle 5. When two circles share a neighbourhood, single flips on them cannot be told apart. The \([[4,2,2]]\) code's one \(Z\) check touches all four qubits, so any one \(X\) error lights it and the puzzle has four equally light answers.
Failure. If the true marks are heavier than the lightest answer, the decoder applies the wrong fix, and the marks plus the fix form a set that lights nothing: an invisible set, a codeword. On the Hamming graph, flips on 5 and 6 light squares 2 and 3 (the digits of 5 and of 6 cancel in square 1), which is the neighbourhood of circle 3, so the decoder flips bit 3 and leaves flips on 3, 5, 6, a codeword (figure 3). A graph of distance \(d\) corrects any \(t\) marks with \(2t < d\), because two different sets of at most \(t\) marks can light the same squares only if their symmetric difference, of size at most \(2t\), is invisible.
Locality. The puzzle is stated in terms of neighbourhoods alone, and the algorithms of part 4 solve it that way: belief propagation lets each square tell each neighbouring circle how likely it is to be marked, given what the square's other neighbours report, and lets each circle sum what it hears. No step looks at the matrix as a whole. The graph is not a picture of the decoder's data structure; it is the data structure.
A CSS code is two graphs on one set of qubits
A CSS code has a matrix \(H_Z\) of \(Z\)-type checks and a matrix \(H_X\) of \(X\)-type checks, both with \(n\) columns. Draw both Tanner graphs on the same \(n\) circles: the \(Z\) squares on one side, the \(X\) squares on the other. By the crossing rule of part 3, an \(X\) error on a qubit marks that circle for the \(Z\) squares only, a \(Z\) error marks it for the \(X\) squares only, and a \(Y\) error marks it for both. The two halves of the syndrome, \(s_Z = H_Z e_X\) and \(s_X = H_X e_Z\), are the lit squares on the two sides (figure 4).
The commutation condition \(H_X H_Z^{\mathsf T} = 0\) is also visible: every \(X\) square and every \(Z\) square must share an even number of circles. On the Shor code each \(X\) square touches six qubits, two whole blocks, and each \(Z\) square touches two neighbouring qubits of one block, so a pair meets in two circles or none. On the Steane code the \(X\) and \(Z\) squares come in pairs with the same four neighbours, and two rows of the Hamming matrix overlap in two places, so every pair meets in four circles or two.
Decoding a CSS code is the puzzle played twice, once on each side, and the three classes of part 2 become statements about the graph. An error on some qubits is detected if it lights a square on the side that can see it. It lights nothing and is harmless if, on that side, it is the symmetric difference of some squares' neighbourhoods, which is to say a product of checks, a stabilizer. It lights nothing and is logical otherwise. The distance is the smallest set of circles of the third kind on either side (figure 5).
Degeneracy has a picture too. On the Shor graph, qubits 1, 2 and 3 have the same neighbourhood on the \(X\) side, the first \(X\) square alone, so a \(Z\) error on any of them lights the same square and the decoder cannot tell them apart (figure 4b). It need not: \(Z_1Z_2\) is the neighbourhood of a \(Z\) square, so the two candidate fixes differ by a stabilizer. Two circles that look alike to one side, and whose pair is a square on the other, can be confused for free.
Layouts that show the structure
A graph can be drawn in any arrangement, and the drawing with qubits in a row and squares above and below is the generic one. For codes with structure a layout that follows it says more (figure 6).
The Shor code as a grid. Put the nine qubits in three rows, one per block. Each \(Z\) square sits between two horizontal neighbours and compares them, which is the three-qubit code run along each row; each \(X\) square sits between two rows and touches all six of their qubits, comparing the phases of the blocks. A bit flip lights the squares on either side of it in its row; a phase flip lights the squares above and below its row.
The Steane code as three faces. Arrange the seven qubits as a triangle: qubits 1, 2 and 4 at the corners, 3, 5 and 6 at the midpoints of the sides, 7 at the centre. Each row of the Hamming matrix is then one of three four-qubit faces, \(\{4,5,6,7\}\), \(\{2,3,6,7\}\) and \(\{1,3,5,7\}\), each a kite from a corner through two midpoints to the centre, and each face carries one \(X\) square and one \(Z\) square. A corner qubit lies in one face, a midpoint in two, the centre in all three, so the lit faces intersect in exactly the flipped qubit: that is the lookup decoder, read off the drawing. This is the smallest instance of the colour codes of Bombín and Martín-Delgado, where the same picture continues on larger triangles.
The surface code as a lattice. Part 4 puts qubits on the edges of a grid, \(Z\) squares on its faces and \(X\) squares on its vertices. There a string of \(X\) errors along a path lights only the faces at its two ends, so decoding becomes pairing up lit endpoints, and a logical operator is a string that crosses the whole lattice with no end to light. The hypergraph product of part 4 builds that lattice as the product of two copies of the repetition graph above.
Two properties of the drawing matter for part 4. The degrees: a code whose squares and circles all have small degree is low-density, each check is measured with few gates and each message-passing step is cheap. And the short cycles: two squares that share two circles form a cycle of length four, which belief propagation handles badly. The repetition graph is a tree; the Hamming graph has a four-cycle through every pair of squares; the lattices of part 4 are chosen to have no four-cycles at all (figure 7).
Interactive figures
Figure A is the Tanner graph of a classical code. Click a bit to flip it: the edges from flipped bits are drawn in colour, every check that meets an odd number of them lights, and the syndrome is read off below. The decoder searches for the lightest set of flips that explains the lit checks and reports whether applying it recovers the message or leaves a codeword. It opens on the Hamming code with bit 5 flipped; try flipping 5 and 6 together, and then the three bits 1, 2, 3.
Figure B is the Tanner graph of a CSS code: qubits in the middle, \(Z\) checks above, \(X\) checks below. Click a qubit to cycle through \(X\), \(Z\) and \(Y\); each side lights independently and the decoder solves each side's puzzle on its own. The Shor and Steane codes and the \([[4,2,2]]\) code can be switched to the grid, face and square layouts described above, with the same error. It opens on the Steane code with \(X_5\): switch to the face layout to see the two lit faces meet at qubit 5.
Problems
Each solution is hidden until you open it. Numbers can be checked against the figures above.
Draw it. (a) Draw the Tanner graph of the three-bit repetition code, \(H_{\text{rep}}\) above, and of the cyclic version with a third row \((1\,0\,1)\). Give the degree of every node. (b) One of the two graphs contains a cycle; which, and how long is it? (c) Mark bits 1 and 3 in each graph. Which squares light?
Solution
(a) Repetition: circles 1 and 3 have degree 1, circle 2 degree 2, both squares degree 2, a path of five nodes. Cyclic: the extra square joins circles 1 and 3, so every circle and every square has degree 2.
(b) The repetition graph is a tree. The cyclic graph is one cycle of length six, circle 1, square 1, circle 2, square 2, circle 3, square 3, back to circle 1.
(c) Repetition: square 1 meets the marks once (circle 1), square 2 once (circle 3): both lit, syndrome 11. Cyclic: the same two squares light, and square 3 meets both marks, so it stays dark: syndrome 110.
Read the matrix off the graph. A graph has four circles and two squares; square 1 touches circles 1, 2, 3 and square 2 touches circles 2, 3, 4. (a) Write \(H\) and find \(k\). (b) Find every invisible set of circles, and hence \(d\). (c) Which single flips can the decoder tell apart, and which not?
Solution
(a) \(H = \begin{pmatrix} 1&1&1&0 \\ 0&1&1&1 \end{pmatrix}\), rank 2, so \(k = 4 - 2 = 2\).
(b) A set lights nothing when each square meets it evenly: \(e_1 + e_2 + e_3 = 0\) and \(e_2 + e_3 + e_4 = 0\), so \(e_1 = e_4\) and \(e_2 + e_3 = e_1\). The solutions are \(0000\), \(0110\), \(1101\) and \(1011\): four codewords, \(2^k\), and the lightest non-empty one has weight 2, so \(d = 2\).
(c) The neighbourhoods are \(\{1\}\), \(\{1,2\}\), \(\{1,2\}\), \(\{2\}\) for circles 1 to 4. Flips on 1 and on 4 have their own syndromes; flips on 2 and on 3 both light both squares and cannot be told apart. That pair, \(0110\), is the lightest invisible set found in (b).
The puzzle by hand. On the Hamming graph of figure A: (a) squares 1 and 2 are lit, nothing else. Which bit does the decoder flip, and why is no other answer as light? (b) All three squares are lit. (c) Bits 5 and 6 are flipped. Work out the lit squares, the decoder's answer, and the net result.
Solution
(a) Lit \(\{1, 2\}\) is the neighbourhood of circle 6, since 6 is \(110\) in binary. Every other single circle lights a different set, and the empty set lights nothing, so flipping bit 6 is the unique lightest answer.
(b) Lit \(\{1, 2, 3\}\) is circle 7's neighbourhood: flip bit 7.
(c) Bit 5 lights \(\{1, 3\}\) and bit 6 lights \(\{1, 2\}\); square 1 meets both marks and stays dark, so the lit set is \(\{2, 3\}\), the neighbourhood of circle 3. The decoder flips bit 3. The net flips \(\{3, 5, 6\}\) are met twice by square 1 (5, 6), twice by square 2 (3, 6) and twice by square 3 (3, 5): a codeword, invisible, and the message has changed. Distance 3 corrects one flip, not two.
Even overlaps. (a) On the Shor graph, count the circles shared by each \(X\) square with each \(Z\) square and confirm that every count is even. (b) Someone proposes an extra \(Z\) check on qubits 3 and 4, across the block boundary. Count its overlaps with the two \(X\) squares. Is it allowed?
Solution
(a) \(X\) square 1 touches qubits 1 to 6 and \(X\) square 2 touches 4 to 9. A \(Z\) square touches a neighbouring pair inside one block, and either both of its qubits lie in a given \(X\) square's two blocks or neither does: every count is 2 or 0.
(b) Qubits 3 and 4 both lie in \(X\) square 1, overlap 2, but only qubit 4 lies in \(X\) square 2, overlap 1. The new check would anticommute with \(X_4 \cdots X_9\), so it is not allowed. On the graph, a square on one side may be added only if it meets every square on the other side evenly.
Degeneracy on the graph. (a) On the Shor graph, group the nine qubits by their neighbourhood on the \(X\) side. (b) A single \(Z\) error lights \(X\) square 2 only. List the lightest explanations and show that any two differ by a product of \(Z\) squares. (c) Now group the qubits by their neighbourhood on the \(Z\) side. Are any two alike?
Solution
(a) Qubits 1, 2, 3 touch \(X\) square 1 only; qubits 4, 5, 6 touch both; qubits 7, 8, 9 touch \(X\) square 2 only. Three groups, one per block.
(b) \(Z_7\), \(Z_8\) or \(Z_9\). \(Z_7Z_8\) and \(Z_8Z_9\) are the neighbourhoods of \(Z\) squares 5 and 6, and \(Z_7Z_9\) is their symmetric difference. Whichever the decoder picks, the net effect is a stabilizer and the state is recovered.
(c) Qubit 1 touches \(Z\) square 1 only, qubit 2 touches squares 1 and 2, qubit 3 square 2 only, and likewise in the other blocks with squares 3, 4 and 5, 6. All nine neighbourhoods are different, so every single bit flip has its own syndrome, as table 4 of part 2 says.
Lit faces on the Steane triangle. Use the face layout of figure B, with faces \(F_1 = \{4,5,6,7\}\), \(F_2 = \{2,3,6,7\}\) and \(F_3 = \{1,3,5,7\}\). (a) Which qubit lies in \(F_1\) and \(F_2\) but not \(F_3\)? Which lies in all three? (b) An \(X\) error on qubit 3 lights which \(Z\) faces, and what is \(s_Z\) as a binary number? (c) State the lookup decoder as a rule about faces. (d) \(X\) errors on qubits 1 and 2 together light which faces, and what does the decoder do?
Solution
(a) Qubit 6 is the midpoint shared by \(F_1\) and \(F_2\). Qubit 7, the centre, lies in all three.
(b) Qubit 3 lies in \(F_2\) and \(F_3\), so those two light: \(s_Z = 011\), which is 3.
(c) Flip the one qubit that lies in every lit face and in no dark face. Corners lie in one face, midpoints in two, the centre in three, and each combination of faces has exactly one such qubit.
(d) Qubit 1 lights \(F_3\) and qubit 2 lights \(F_2\): both light. The qubit in exactly those faces is 3, so the decoder applies \(X_3\), leaving \(X_1X_2X_3\): the logical \(\bar X\) of part 3. Two errors beat a distance-3 code.
Cycles. (a) Show that the Hamming graph has a cycle of length four through every pair of squares, and count them. (b) Does the Shor graph, taken one side at a time, have any four-cycles? (c) Why does part 4 care?
Solution
(a) Rows 1 and 2 share columns 6 and 7, so square 1, circle 6, square 2, circle 7 is a four-cycle. Rows 1 and 3 share 5 and 7, rows 2 and 3 share 3 and 7. Each pair of squares shares exactly two circles and so gives exactly one four-cycle: three in all.
(b) No. On the \(Z\) side two squares share at most one qubit (neighbouring pairs in a block overlap in one qubit). On the \(X\) side there are only two squares, sharing qubits 4, 5, 6, which does make a four-cycle through any two of them: three four-cycles on that side. So the \(Z\) side is free of them and the \(X\) side is not.
(c) Belief propagation is exact on a tree and approximate otherwise; the shorter the cycles, the sooner a message returns to the node it came from and gets counted twice. Four-cycles are the worst case, which is why the codes of part 4 are built without them.
References
- R. M. Tanner, “A recursive approach to low complexity codes”, IEEE Trans. Inf. Theory 27, 533 (1981). doiThe graph itself, introduced to build long codes from short ones and decode them locally.
- F. R. Kschischang, B. J. Frey and H.-A. Loeliger, “Factor graphs and the sum-product algorithm”, IEEE Trans. Inf. Theory 47, 498 (2001). doiMessage passing on the graph, the general form of the belief propagation of part 4.
- T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge University Press (2008). doiThe textbook on LDPC codes and their graphs; chapter 2 covers factor graphs and chapter 3 binary erasure decoding on them.
- H. Bombin and M. A. Martin-Delgado, “Topological quantum distillation”, Phys. Rev. Lett. 97, 180501 (2006). arXiv:quant-ph/0605138 · doiColour codes; the Steane code drawn as three faces is their smallest example.
- N. P. Breuckmann and J. N. Eberhardt, “Quantum low-density parity-check codes”, PRX Quantum 2, 040101 (2021). arXiv:2103.06309 · doiTanner graphs of CSS codes and the chain-complex view behind the products of part 4.