Notes on quantum error correction · Part 4 · beyond Roffe's guide · previous: Part 3
Quantum LDPC codes
A code is low-density parity-check (LDPC) when every check touches only a few qubits and every qubit sits in only a few checks, however large the code grows. The surface code is one, but it encodes a single qubit. This part asks how to keep the checks small while encoding many qubits, builds the simplest general answer, the hypergraph product, and decodes it with belief propagation. The interactive figure is at the end, followed by problems and references.
What LDPC buys, and what it costs
A family of CSS codes is LDPC if the rows and columns of \(H_X\) and \(H_Z\) have weight at most some constant \(w\) independent of \(n\). Each stabilizer measurement then touches at most \(w\) qubits, syndrome extraction runs in constant depth, and an error on one ancilla spreads to few data qubits. Classically, LDPC codes decoded by belief propagation come close to the channel capacity (Gallager 1962), which is why they are in every modern communication standard.
The surface code is LDPC with \(w = 4\) but has \(k = 1\) and \(d \sim \sqrt n\). That is not an accident of design: any stabilizer code whose checks are local on a two-dimensional lattice obeys \(k d^2 = O(n)\) (Bravyi, Poulin and Terhal 2010). Encoding many qubits at large distance with small checks therefore requires checks that are not local in the plane, and a construction that controls both \(k\) and \(d\).
Why not take two classical LDPC codes?
Part 3 builds a CSS code from any \(H_X, H_Z\) with \(H_X H_Z^{\mathsf T} = 0\). Two independently chosen sparse matrices almost never satisfy that, and choosing \(H_X = H_Z = H\) with \(H H^{\mathsf T} = 0\) forces the classical code to contain its own dual, which for sparse \(H\) puts low-weight words among the logical operators. Early constructions such as the bicycle codes of MacKay, Mitchison and McFadden (2004) designed matrices around this condition. The hypergraph product meets it by construction.
The hypergraph product
Given two classical codes with parity-check matrices \(H_1\) (\(m_1 \times n_1\)) and \(H_2\) (\(m_2 \times n_2\)), Tillich and Zémor define
\[ \begin{aligned} H_X &= \bigl(\, H_1 \otimes I_{n_2} \;\big|\; I_{m_1} \otimes H_2^{\mathsf T} \,\bigr), \\ H_Z &= \bigl(\, I_{n_1} \otimes H_2 \;\big|\; H_1^{\mathsf T} \otimes I_{m_2} \,\bigr). \end{aligned} \]Then \(H_X H_Z^{\mathsf T} = H_1 \otimes H_2^{\mathsf T} + H_1 \otimes H_2^{\mathsf T} = 0\) over \(\mathbb F_2\), whatever \(H_1\) and \(H_2\) are. The qubits come in two blocks, one for each pair (bit of code 1, bit of code 2) and one for each pair (check of code 1, check of code 2), and the parameters are
\[ \begin{aligned} n &= n_1 n_2 + m_1 m_2, \\ k &= k_1 k_2 + k_1^{\mathsf T} k_2^{\mathsf T}, \\ d &= \min\bigl(d_1, d_2, d_1^{\mathsf T}, d_2^{\mathsf T}\bigr), \end{aligned} \]where \(k_i^{\mathsf T}\) and \(d_i^{\mathsf T}\) belong to the transposed code \(\ker H_i^{\mathsf T}\) (a distance counts as \(\infty\) when that code is empty). An X check has weight equal to a row weight of \(H_1\) plus a column weight of \(H_2\), so sparse inputs give a sparse output. The product of two repetition codes is exactly the planar surface code, and the product of two cyclic repetition codes is Kitaev's toric code. Feeding in classical LDPC codes with \(k, d \propto n\) gives \(k \propto N\) and \(d \propto \sqrt N\) in the number of qubits \(N\): constant rate, at the surface code's distance scaling.
| code | \([[n,k,d]]\) | rate \(k/n\) | largest check weight | largest qubit degree |
|---|---|---|---|---|
| HGP(rep 3, rep 3): surface code | [[13, 1, 3]] | 0.077 | 4 | 4 |
| HGP(rep 5, rep 5): surface code | [[41, 1, 5]] | 0.024 | 4 | 4 |
| HGP(ring 4, ring 4): toric code | [[32, 2, 4]] | 0.063 | 4 | 4 |
| HGP(Hamming, rep 3) | [[27, 4, 3]] | 0.148 | 6 | 6 |
| HGP(Hamming, Hamming) | [[58, 16, 3]] | 0.276 | 7 | 8 |
| Bivariate bicycle code (Bravyi et al. 2024) | [[144, 12, 12]] | 0.083 | 6 | 6 |
All rows except the last are computed by these notes' own code; the product distances are checked by exhaustive search where the code is small enough. For comparison, twelve logical qubits at distance 12 in the planar surface code of Roffe's section 5 take twelve patches of \(12^2 + 11^2 = 265\) data qubits, 3,180 in all, against 144 for the bivariate bicycle code.
Beyond the hypergraph product
The \(\sqrt N\) distance of the hypergraph product was a barrier for a decade. Lifted-product and related constructions, which replace the entries of the matrices by elements of a group algebra, removed it: Panteleev and Kalachev (2022) gave families with \(k \propto N\) and \(d \propto N\), asymptotically good quantum LDPC codes. On the practical side, codes with constant rate reduce the overhead of fault tolerance to a constant factor (Gottesman 2013), and small quasi-cyclic codes such as the bivariate bicycle codes are designed for hardware with a few long-range couplers per qubit. Breuckmann and Eberhardt's review covers these constructions.
Decoding with belief propagation
By part 3, decoding \(X\) errors means solving \(H_Z \hat e = s_Z\) for a likely \(\hat e\), a classical problem on the Tanner graph of \(H_Z\) (part 2.5: qubits on one side, checks on the other). Belief propagation passes log-likelihood ratios along its edges. Each qubit starts from \(L_0 = \ln\frac{1-p}{p}\). In the min-sum form used in the figure, a check \(c\) with syndrome bit \(s_c\) tells each neighbour \(v\)
\[ r_{c\to v} = (-1)^{s_c}\,\alpha\goodbreak \prod_{v' \in N(c)\setminus v} \operatorname{sgn} q_{v'\to c} \;\goodbreak\min_{v' \in N(c)\setminus v} |q_{v'\to c}| , \]each qubit sums what it hears,
\[ L_v = L_0 + \sum_{c \in N(v)} r_{c\to v}, \qquad q_{v\to c} = L_v - r_{c\to v}, \]and the hard decision \(\hat e_v = [L_v < 0]\) is checked against the syndrome after every round, stopping when \(H_Z \hat e = s_Z\). The figure uses \(\alpha = 0.75\) and at most 30 rounds. Classically this is fast and near-optimal on sparse graphs. On quantum codes it runs into two problems, both visible in the figure.
- Degeneracy. Errors that differ by a stabilizer are equally good answers, so the beliefs can split evenly between them and never settle. On the distance-5 surface code, HGP(rep 5, rep 5), BP decodes every single \(X\) error, yet 146 of the 820 two-qubit \(X\) errors, which the code can correct, leave it without a syndrome-matching answer after 30 rounds; \(X\) on qubits 1 and 2 is one.
- BP is not a minimum-weight decoder. It stops at the first hard decision that matches the syndrome. On HGP(Hamming, Hamming), 7 of the 58 single \(X\) errors are decoded wrongly: \(X\) on qubit 7 violates three checks, after one round qubits 3, 5, 6 and 7 all look flipped, their syndrome happens to match, and the weight-four guess differs from the truth by a logical operator.
The standard remedy is BP followed by ordered-statistics decoding (BP+OSD): when BP fails, its soft output ranks the qubits by how likely they are to be flipped, and Gaussian elimination solves \(H \hat e = s\) using the most likely qubits first. Panteleev and Kalachev introduced it for quantum LDPC codes, and Roffe and coauthors benchmarked it across code families with an open-source implementation.
Interactive figure
Choose two classical codes; the figure lays out their hypergraph product on a grid whose rows follow code 1 (bits and checks) and whose columns follow code 2. Bit-bit and check-check positions hold qubits, check-bit positions hold X checks, bit-check positions hold Z checks. For two repetition codes this is the surface-code lattice; for the Hamming code the checks reach across the grid, which a hover over a square shows. Click qubits to place errors, or sample them at rate \(p\), then decode with BP and scrub through the iterations: the rings show each qubit's belief that it carries an \(X\) (inner) or \(Z\) (outer) error. To reproduce the failures above, choose rep 5 for both codes and put \(X\) on qubits 1 and 2, or Hamming for both and put \(X\) on qubit 7.
Problems
Each solution is hidden until you open it. Numbers can be checked against the figures above.
Why the hypergraph product always commutes. Using \((A\otimes B)(C\otimes D) = AC\otimes BD\), show that \(H_X H_Z^{\mathsf T} = 0\) over \(\mathbb F_2\) for any \(H_1\) and \(H_2\).
Solution
Multiply block by block:
\[ H_X H_Z^{\mathsf T} = (H_1\otimes I)(I\otimes H_2^{\mathsf T}) + (I\otimes H_2^{\mathsf T})(H_1\otimes I) = H_1\otimes H_2^{\mathsf T} + H_1\otimes H_2^{\mathsf T} = 0 , \]since every entry appears twice and \(1 + 1 = 0\). The left blocks have \(n_1 n_2\) columns and the right blocks \(m_1 m_2\), which is where \(n = n_1n_2 + m_1m_2\) comes from.
The surface and toric codes as products. Let \(H_{\text{rep}} = \begin{pmatrix}1&1&0\\0&1&1\end{pmatrix}\), and let \(H_{\text{ring}}\) be the \(4\times4\) matrix with rows \(1100, 0110, 0011, 1001\). (a) Find \(n, k, d\) of each code and \(k^{\mathsf T}, d^{\mathsf T}\) of its transpose. (b) Use the formulas to get the parameters of HGP(rep, rep) and HGP(ring, ring).
Solution
(a) Repetition: \(m = 2\), \(n = 3\), rank 2, so \(k = 1\) and \(d = 3\). Its transpose is \(3\times2\) with rank 2, so \(k^{\mathsf T} = 2 - 2 = 0\) and \(d^{\mathsf T} = \infty\). Ring: the four rows sum to zero, so the rank is 3, \(k = 1\) (the word \(1111\)) and \(d = 4\); the transpose is again a ring, with \(k^{\mathsf T} = 1\) and \(d^{\mathsf T} = 4\).
(b) HGP(rep, rep): \(n = 9 + 4 = 13\), \(k = 1\cdot1 + 0\cdot0 = 1\), \(d = \min(3, 3, \infty, \infty) = 3\): the \([[13,1,3]]\) surface code. HGP(ring, ring): \(n = 16 + 16 = 32\), \(k = 1 + 1 = 2\), \(d = 4\): the \([[32,2,4]]\) toric code, with its two logical qubits from the two cycles of the torus.
Rate: the Hamming product. (a) Find the parameters of HGP(Hamming, Hamming). (b) Find its largest check weight and largest qubit degree. (c) How many qubits would sixteen Steane codes need to protect the same number of logical qubits at the same distance?
Solution
(a) The Hamming matrix is \(3\times7\) with rank 3: \(k = 4\), \(d = 3\), and its transpose has \(k^{\mathsf T} = 0\), \(d^{\mathsf T} = \infty\). So \(n = 49 + 9 = 58\), \(k = 16 + 0 = 16\), \(d = 3\).
(b) An \(X\) check has weight (row weight of \(H_1\)) + (column weight of \(H_2\)) \(= 4 + 3 = 7\) at most. A check-check qubit lies in one \(X\) check per 1 in a row of \(H_2\) and one \(Z\) check per 1 in a row of \(H_1\): \(4 + 4 = 8\).
(c) \(16 \times 7 = 112\) qubits, against 58: the rate \(16/58 \approx 0.28\) is almost double the Steane code's \(1/7\).
Belief propagation by hand. Decode the classical repetition code \(H = \begin{pmatrix}1&1&0\\0&1&1\end{pmatrix}\) with \(p = 0.1\) after a flip of bit 1, so \(s = (1, 0)\). Run min-sum with \(\alpha = 0.75\), as the figure does, for two iterations: give the messages, the \(L_v\) and the hard decision after each.
Solution
\(L_0 = \ln 9 \approx 2.197\), and every \(q_{v\to c}\) starts at \(L_0\).
Iteration 1. Check 1 (\(s = 1\)) sends \(-0.75 \times 2.197 = -1.648\) to bits 1 and 2; check 2 (\(s = 0\)) sends \(+1.648\) to bits 2 and 3. So \(L = (0.549,\ 2.197,\ 3.845)\): no bit looks flipped, the syndrome is not matched, and BP continues. The new messages \(q_{v\to c} = L_v - r_{c\to v}\) are \(q_{1\to1} = 2.197\), \(q_{2\to1} = 3.845\), \(q_{2\to2} = 0.549\), \(q_{3\to2} = 2.197\).
Iteration 2. Check 1 sends \(-0.75 \times 3.845 = -2.884\) to bit 1 and \(-0.75 \times 2.197 = -1.648\) to bit 2; check 2 sends \(+1.648\) to bit 2 and \(+0.75 \times 0.549 = 0.412\) to bit 3. Now \(L = (-0.687,\ 2.197,\ 2.609)\), the hard decision is \(100\), and it matches the syndrome: converged in two iterations. Bit 2 hears opposite advice from its two checks, grows confident it is clean, and that confidence is what convinces check 1 to blame bit 1. With \(\alpha = 1\) the first iteration would end in a tie at \(L_1 = 0\).
Degeneracy and belief propagation. Two errors \(E\) and \(E' = ES\), with \(S\) a stabilizer, have the same weight, the same syndrome and the same prior probability. Explain why belief propagation can stall on such a pair, why a minimum-weight decoder would not mind, and what ordered-statistics decoding adds.
Solution
BP computes per-qubit marginals from local messages. When \(E\) and \(E'\) are equally likely and nothing else competes, the messages are symmetric under swapping them, so the qubits where they differ end up near probability \(\tfrac12\). Rounding each marginal separately then picks parts of both, a pattern that matches neither syndrome, and the iterations can oscillate instead of settling.
A minimum-weight decoder returns \(E\) or \(E'\), and either is a correct recovery because they differ by a stabilizer (eq. 37). The trouble is particular to deciding qubit by qubit.
OSD uses BP's soft output only to rank the qubits, then solves \(H\hat e = s\) exactly by Gaussian elimination on the most likely columns. The result always matches the syndrome, and the ranking breaks the tie in favour of one of the two equivalent answers.
References
- N. P. Breuckmann and J. N. Eberhardt, “Quantum low-density parity-check codes”, PRX Quantum 2, 040101 (2021). arXiv:2103.06309 · doiThe best entry point: a review of quantum LDPC constructions, their parameters and decoders.
- J.-P. Tillich and G. Zémor, “Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength”, IEEE Trans. Inf. Theory 60, 1193 (2014). arXiv:0903.0566 · doiThe hypergraph product and its parameters.
- D. J. C. MacKay, G. Mitchison and P. L. McFadden, “Sparse-graph codes for quantum error correction”, IEEE Trans. Inf. Theory 50, 2315 (2004). arXiv:quant-ph/0304161 · doiEarly sparse-graph quantum codes, and why the commutation condition makes them hard to design.
- S. Bravyi, D. Poulin and B. Terhal, “Tradeoffs for reliable quantum information storage in 2D systems”, Phys. Rev. Lett. 104, 050503 (2010). arXiv:0909.5200The bound k d² = O(n) for codes with local checks in two dimensions.
- A. Yu. Kitaev, “Fault-tolerant quantum computation by anyons”, Ann. Phys. 303, 2 (2003). arXiv:quant-ph/9707021 · doiThe toric code, the hypergraph product of two cyclic repetition codes.
- R. G. Gallager, “Low-density parity-check codes”, IRE Trans. Inf. Theory 8, 21 (1962). doiClassical LDPC codes and iterative decoding.
- D. Gottesman, “Fault-tolerant quantum computation with constant overhead”, preprint (2013). arXiv:1310.2984Why constant-rate LDPC codes make fault tolerance cheap.
- P. Panteleev and G. Kalachev, “Degenerate quantum LDPC codes with good finite length performance”, Quantum 5, 585 (2021). arXiv:1904.02703 · doiBP+OSD decoding for quantum LDPC codes.
- J. Roffe, D. R. White, S. Burton and E. T. Campbell, “Decoding across the quantum low-density parity-check code landscape”, Phys. Rev. Research 2, 043423 (2020). arXiv:2005.07016 · doi · software: github.com/quantumgizmos/ldpcA benchmark of BP+OSD across hypergraph-product and other codes, with software.
- P. Panteleev and G. Kalachev, “Asymptotically good quantum and locally testable classical LDPC codes”, in Proc. 54th ACM STOC (2022). arXiv:2111.03654The first asymptotically good quantum LDPC codes.
- S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall and T. J. Yoder, “High-threshold and low-overhead fault-tolerant quantum memory”, Nature 627, 778 (2024). arXiv:2308.07915 · doiThe [[144,12,12]] bivariate bicycle code and its syndrome circuits.