7 Quantum LDPC and Tanner Codes
After completing this chapter, you will be able to: - Explain the challenges of constructing quantum LDPC codes - Apply the hypergraph product construction to build quantum codes - Describe quantum Tanner codes and their use of expander graphs - Analyze the parameters of “good” qLDPC codes (linear distance, constant rate) - Compare the overhead of qLDPC codes versus surface codes
This chapter assumes familiarity with: - CSS code construction (Chapter 3) - Classical LDPC codes and Tanner graphs (Chapter 2) - Surface code basics (Chapter 4)
Classical LDPC codes achieve near-Shannon-limit performance with low-complexity decoding. Extending this success to quantum codes is one of the most important open problems in quantum error correction. This chapter presents the key constructions and the recent breakthrough in “good” quantum LDPC codes.
7.1 From Classical to Quantum LDPC
The transition from classical to quantum LDPC codes is subtle due to the non-abelian nature of quantum operators.
7.1.1 Classical LDPC Advantages
Recall the advantages of classical LDPC codes from Chapter 2:
- Sparse parity checks: Each check involves only a few bits
- Linear-time encoding: Using efficient preprocessing
- Near-Shannon-limit performance: Achieving rates close to capacity
- Parallel decoding: Belief propagation converges quickly
These properties make LDPC codes practically ideal for classical communications.
Classical LDPC codes are like a neighborhood watch: each resident (check) only monitors a few houses (bits), but collectively they detect any intrusion (error). The sparse connections mean communication is fast and local. Quantum LDPC codes need the same efficiency, but with the added complication that the “neighborhood watch” for X errors and Z errors must not interfere with each other.
7.1.2 Quantization Challenges
Quantum codes face additional constraints that make direct quantization difficult.
A quantum LDPC code must satisfy the CSS condition: The X-type and Z-type stabilizer matrices must be orthogonal: $ H_X H_Z^T = 0 $
This ensures that X-type and Z-type stabilizers commute.
The CSS condition is equivalent to: $ C(H_Z) ⊂ C(H_X^T) $ where \(C(H)\) is the column space of \(H\)
Or equivalently: \(im(H_Z) ⊂ im(H_X)\) over GF(2) after appropriate mapping.
This constraint means we cannot simply take two independent classical LDPC codes. The quantum code must be carefully constructed.
7.2 Example: Naive Quantum LDPC Fails
If we take: - \(H_X\) = random LDPC parity-check matrix - \(H_Z\) = random LDPC parity-check matrix
Then with high probability \(H_X H_Z^T \neq 0\), violating the CSS condition.
The matrices must have specific structure to commute.
“Any two sparse matrices can work as X and Z checks.” The CSS constraint \(H_X H_Z^T = 0\) is a global condition: it couples the structure of both matrices. You cannot design \(H_X\) and \(H_Z\) independently — they must be jointly constructed to ensure every X-check overlaps with every Z-check an even number of times. This is why simple random constructions fail.
7.2.1 Sparse Stabilizer Requirement
For practical decoding, we need stabilizers that are both commuting and sparse.
A quantum LDPC code is a stabilizer code where: - All stabilizer generators have bounded weight (sparse) - Each qubit participates in a bounded number of stabilizers
This enables efficient syndrome extraction and decoding.
The key difference from the surface code: - Surface code: fixed lattice structure, local interactions - General qLDPC: arbitrary sparse graphs, potentially long-range connections
The surface code is itself a qLDPC code with: - Stabilizer weight: 4 (each vertex/face involves 4 edges) - Qubit degree: 4 (each edge touches 2 vertices and 2 faces)
But it encodes only \(k = O(1)\) logical qubits with \(n\) physical qubits.
7.3 Hypergraph Product Construction
The hypergraph product, introduced by Tillich and Zémor @tillich2014, provides a systematic way to construct quantum LDPC codes from classical codes.
7.3.1 Classical Product Constructions
First, recall the classical product constructions.
For matrices \(A\) (size \(m × n\)) and \(B\) (size \(p × q\)), the tensor product is: $ A ⊗ B = mat( a_(1,1)B, …, a_(1,n)B; … , …, …; a_(m,1)B, …, a_(m,n)B ) $
Size: \((m p) × (n q)\)
The Kronecker product \(A ⊠ B\) of classical parity-check matrices gives a classical LDPC code with improved properties.
7.3.2 Hypergraph Product Definition
The quantum hypergraph product generalizes this to give both X and Z checks.
Let \(H\) be a classical parity-check matrix of size \(r × n\) with no all-zero columns. The hypergraph product produces quantum codes:
X-type checks: \(H_X = H ⊗ I_n\) (size \(r n × n^2\)) Z-type checks: \(H_Z = I_r ⊗ H\) (size \(r n × n^2\))
These automatically satisfy \(H_X H_Z^T = 0\).
The hypergraph product matrices commute: $ (H I_n) (I_r H^T) = H H^T $
Since \(H H^T\) is symmetric over GF(2), this equals its transpose, ensuring the CSS condition holds.
The hypergraph product is like weaving two baskets together. If you take one basket and stretch it horizontally (that’s \(H \otimes I\)), and another basket and stretch it vertically (\(I \otimes H\)), the horizontal strands always cross vertical strands at right angles — they never clash. This geometric arrangement guarantees that the X-type and Z-type constraints don’t fight each other. The product structure is what makes the CSS condition automatically satisfied.
7.4 Example: Small Hypergraph Product
Let \(H = [1, 1, 1]\) (repetition code, \(r=1, n=3\)):
\(H_X = [1,1,1] \otimes I_3 = [I_3, I_3, I_3]\) (3 checks, 9 qubits) \(H_Z = I_1 \otimes [1,1,1] = [1,1,1] \otimes I_3\) (same)
This gives a \([[9, 1, 3]]\) Shor-like code with weight-3 stabilizers.
7.4.1 Code Parameters
The hypergraph product gives predictable parameters.
If \(H\) is an \([n, n-r]\) classical code with minimum distance \(d\): - \(n_q = n^2\) physical qubits - \(r_q = 2r n\) stabilizer generators - \(k_q = n^2 - 2r n + 1\) logical qubits - Distance \(d_q = d\)
More precisely, for the [[n, k, d]] notation: - \(n = n^2\) - \(k = 1\) (typically, for good choices of H) - \(d = d\) (from classical code distance)
7.5 Example: From [7,4,3] Hamming Code
Let \(H\) be the \([7, 4, 3]\) Hamming code parity-check matrix: - \(n = 7\), \(r = 3\) - Hypergraph product gives: - \(n_q = 49\) qubits - \(r_q = 42\) checks - \(k_q = 49 - 42 = 7\) logical qubits - \(d_q = 3\)
Result: \([[49, 7, 3]]\) code
7.5.1 Worked Example: Hypergraph Product from Hamming Code
Let us construct a quantum code step-by-step using the hypergraph product applied to the \([7, 4, 3]\) Hamming code.
Step 1: Start with the classical Hamming code parity-check matrix. The \([7, 4, 3]\) Hamming code has parity-check matrix: $ H = mat( 1, 1, 1, 0, 1, 0, 0; 0, 1, 1, 1, 0, 1, 0; 1, 1, 0, 1, 0, 0, 1 ) $
Here \(r = 3\) checks and \(n = 7\) codeword bits.
Step 2: Construct the X-type check matrix. $ H_X = H ⊗ I_7 $
This creates a \(21 × 49\) matrix. Each row of \(H\) becomes 7 rows, and each column becomes 7 columns. Explicitly, the first 7 rows are: $ mat( 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, …, 0, 0; 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, …, 0, 0; “…” (“continuing pattern”) ) $
Each X-check involves exactly 7 qubits (the LDPC property).
Step 3: Construct the Z-type check matrix. $ H_Z = I_3 ⊗ H $
This creates a \(21 × 49\) matrix where each of the 3 rows repeats 7 times. The first 7 rows are all identical to row 1 of \(H\), the next 7 to row 2, etc.
Step 4: Verify the CSS condition. $ H_X H_Z^T = (H ⊗ I_7) (I_3 ⊗ H^T) = H ⊗ H^T $
Since \(H H^T\) is symmetric over GF(2), we have \(H_X H_Z^T = (H_X H_Z^T)^T\), which means all entries are 0 (the CSS condition holds).
Step 5: Compute the code parameters. - Physical qubits: \(n = 7^2 = 49\) - Stabilizer generators: \(r = 2 × 3 × 7 = 42\) (21 X-type + 21 Z-type) - Logical qubits: \(k = 49 - 42 = 7\) - Distance: \(d = 3\) (inherited from Hamming code)
Result: \(qcodeparam(49, 7, 3)\) quantum code.
Step 6: List the first few stabilizer generators. The \(21\) X-type generators from \(H_X = H ⊗ I_7\) each have weight 7. The first six X-stabilizers (from the first row of \(H\)) are: $ S_X^1 = X_1 X_5 X_9, quad S_X^2 = X_2 X_6 X_10, quad S_X^3 = X_3 X_7 X_11, quad S_X^4 = X_4 X_8 X_12, quad S_X^5 = X_5 X_9 X_13, quad S_X^6 = X_6 X_10 X_14 $
Similarly, the \(21\) Z-type generators from \(H_Z = I_3 ⊗ H\) each have weight 3. The first six Z-stabilizers are: $ S_Z^1 = Z_1 Z_2 Z_3, quad S_Z^2 = Z_8 Z_9 Z_10, quad S_Z^3 = Z_15 Z_16 Z_17, quad S_Z^4 = Z_4 Z_5 Z_6, quad S_Z^5 = Z_11 Z_12 Z_13, quad S_Z^6 = Z_18 Z_19 Z_20 $
These explicit generators show the LDPC structure: each X-stabilizer involves 7 qubits, while each Z-stabilizer involves 3 qubits (the weight of the original Hamming code).
Step 7: Interpret the structure. The resulting code is like a grid of Hamming codes: - X-checks run along rows, each checking 7 qubits in a row - Z-checks run along columns, each checking 7 qubits in a column
The 7 logical qubits correspond to the 4-bit message space plus 3 bits of redundancy from the classical code.
The hypergraph product is like taking two sheets of graph paper and overlaying them at 90 degrees. One sheet has the horizontal constraints (X checks), the other has vertical constraints (Z checks). Where they intersect, the qubit participates in both types of checks. The tensor product structure guarantees that horizontal and vertical constraints never “fight” each other — they always commute.
7.5.2 Mathematical Properties of Hypergraph Product
The hypergraph product has several important mathematical properties that guarantee its correctness.
Let \(H\) be an \(r × n\) classical parity-check matrix. Then: $ H_X H_Z^T = (H ⊗ I_n)(I_r ⊗ H^T) = H ⊗ H^T $
Over GF(2), \(H H^T\) is always symmetric because \((H H^T)^T = H H^T\). The symmetry implies that \(H_X H_Z^T\) has zero diagonal entries when \(H\) has no all-zero columns, which ensures the CSS condition \(H_X H_Z^T = 0\).
More precisely: For any \(i,j\), the \((i,j)\)-block of \(H_X H_Z^T\) is \(H_{i}·H_{j}^T\) where \(H_i\) is row \(i\) of \(H\). This equals its transpose because inner products are symmetric over GF(2).
If \(H\) has row weight \(w\) (each check involves \(w\) bits) and column weight \(d\): - X-type stabilizers from \(H ⊗ I_n\) have weight \(w · n\) (each row expanded \(n\) times) - Z-type stabilizers from \(I_r ⊗ H\) have weight \(d\) (unchanged)
For good LDPC codes with bounded weights, the quantum stabilizers have bounded weight, preserving the LDPC property.
The asymmetry in stabilizer weights (X-checks are heavier than Z-checks) is a feature, not a bug. Both types of errors must be caught, and the code distance accounts for both. The minimum distance bounds both X and Z error correction capability.
7.5.3 Limitations of Hypergraph Product
The hypergraph product has an important limitation.
“Good classical LDPC codes automatically give good quantum LDPC codes.” While classical good codes have constant rate and distance growing with n, when used in the hypergraph product, they produce quantum codes with constant rate but distance that doesn’t grow — it stays at the classical distance. This is because each error in the classical code maps directly to an error in the quantum code, so the quantum distance is bounded by the classical distance. To get good quantum codes, we need fundamentally different constructions that exploit graph topology in new ways.
For the hypergraph product from classical code \(C\): - If \(C\) has distance \(d\), the quantum code has distance \(d\) - But the number of logical qubits \(k\) grows as \(O(n)\)
The rate \(R = k/n\) is bounded away from zero for good classical codes, but the distance only grows as \(d = O(1)\) for fixed-rate codes.
This gives \(R > 0\) but \(d = O(1)\), not a “good” code.
Consider the hypergraph product \(Q = cal(H)(C)\) where \(C\) is an \([n, k, d]\) classical code. The quantum distance \(d_q\) satisfies \(d_q ≤ d\) because: - Any weight-\(d\) error in the classical code becomes a weight-\(d\) X-error in the quantum code - This error anticommutes with some Z-stabilizer, detected as a syndrome
Since classical good codes have constant distance \(d = O(1)\), the quantum code inherits this limitation.
This limitation motivated the search for better constructions—the quantum Tanner codes.
7.6 Quantum Tanner Codes
Quantum Tanner codes, developed by Leverrier and Zémor @leverrier2015, combine the classical Tanner code construction with quantum constraints.
7.6.1 Classical Tanner Codes Review
First, recall the classical Tanner code structure.
A Tanner graph consists of: - Variable nodes (codeword bits) - Check nodes (parity constraints) - Edges connecting variables to checks
The code consists of all assignments satisfying all check constraints.
Let \(C\) be a classical linear code with parity-check matrix \(H\). Let \(T\) be a graph where each edge of \(T\) corresponds to a position in \(H\).
The Tanner code from \((H, T)\) enforces: - Each variable node satisfies all incident checks - Each check node enforces parity of incident variables
This is a product construction that can achieve good distance.
The key insight: recursively applying the Tanner construction amplifies distance.
7.6.2 Quantum Tanner Code Construction
The quantum Tanner code combines two Tanner constructions that satisfy the CSS constraint.
Let \(C_X\) and \(C_Z\) be two classical Tanner codes with: - Same underlying graph structure - \(C_Z ⊂ C_X\) (containment for CSS condition)
The quantum Tanner code has: - X-type stabilizers from \(C_X^⊥\) - Z-type stabilizers from \(C_Z\)
Parameters depend on the classical Tanner codes.
If \(C_X\) has parameters \([n, k_X, d_X]\) and \(C_Z\) has \([n, k_Z, d_Z]\) with \(C_Z ⊂ C_X\), then the quantum Tanner code is \([[n, k_X - k_Z, min(d_X, d_Z^⊥)]]\).
The quantum distance is bounded by the classical distances.
7.7 Example: Small Quantum Tanner Code
Let \(C_X\) be a \([7, 4, 3]\) Hamming code and \(C_Z = C_X^⊥\) (simplex code): - \(k_X = 4\), \(k_Z = 3\) → \(k_q = 1\) - \(d_X = 3\), \(d_Z = 4\) → \(d_q = 3\)
This recovers the Steane code \([[7, 1, 3]]\)!
7.7.1 Worked Example: CSS Code from Two Classical Codes
The most common way to construct CSS codes also provides insight into the quantum Tanner construction. Let us build the Steane code step-by-step from two classical codes.
Step 1: Choose two classical codes with containment. Let \(C_1\) be the \([7, 4, 3]\) Hamming code and \(C_2 = C_1^⊥\) be its dual (the \([7, 3, 4]\) simplex code). Verify: \(C_2 ⊂ C_1\) because the simplex code is contained in the Hamming code.
Step 2: Define the X and Z stabilizers. The CSS construction gives: - X-type stabilizers: From codewords in \(C_2^⊥ = C_1\) - Z-type stabilizers: From codewords in \(C_2\)
Explicitly, the parity-check matrices are: $ H_X = H_“Hamming” = mat( 1, 1, 1, 0, 1, 0, 0; 0, 1, 1, 1, 0, 1, 0; 1, 1, 0, 1, 0, 0, 1 ) $
$ H_Z = G_“Hamming”^T = mat( 1, 0, 0, 0, 1, 0, 1; 0, 1, 0, 0, 1, 1, 1; 0, 0, 1, 0, 1, 1, 0; 0, 0, 0, 1, 0, 1, 1 ) $
Step 3: Verify the CSS condition. Check that \(H_X H_Z^T = 0\): Each row of \(H_X\) is orthogonal to each row of \(H_Z\) because \(C_2 ⊂ C_1\).
Step 4: Compute parameters. - Total qubits: \(n = 7\) - X stabilizers: \(3\) (rank of \(H_X\)) - Z stabilizers: \(3\) (rank of \(H_Z\), but one is dependent) - Logical qubits: \(k = 7 - 3 - 3 + 1 = 1\) - Distance: \(d = 3\)
Result: \(qcodeparam(7, 1, 3)\) — the Steane code!
Step 5: Connection to Tanner codes. The Steane code can be viewed as a quantum Tanner code where: - The base graph is the complete graph on 7 vertices - Local codes enforce Hamming constraints - Containment \(C_2 ⊂ C_1\) ensures the CSS condition
Building a CSS code from two classical codes is like nesting two dolls. The inner doll (\(C_2\)) must fit entirely inside the outer doll (\(C_1\)). The space between the dolls — the set of codewords in \(C_1\) but not in \(C_2\) — encodes the quantum information. Neither classical code alone can protect quantum information, but together they create a “safe house” where logical states are protected from both X and Z errors.
7.7.2 Expander Graphs and Quantum Tanner Codes
The key to achieving good distance in quantum Tanner codes lies in the use of expander graphs.
A \(d\)-regular graph \(G = (V, E)\) is an expander if there exists \(ε > 0\) such that for every subset \(S ⊆ V\) with \(|S| ≤ |V|/2\): \(|∂S| ≥ ε|S|\)
where \(∂S\) is the edge boundary (edges from \(S\) to \(V \ S\)).
The constant \(ε\) is called the expansion factor or isoperimetric number.
A \(d\)-regular graph is a spectral expander if the second smallest eigenvalue of its adjacency matrix satisfies: \(λ_2 ≥ c · d\) for some constant \(c > 0\)
The spectral gap \(d - λ_2\) measures how “mixing” the graph is. Larger spectral gap implies better expansion.
Think of an expander graph like a densely connected social network. In a regular social network, a small group of people might be isolated from the rest — they only know each other. In an expander graph, even the smallest group has many connections outside the group. If you’re trying to find information about any person in the network (detect an error), you can reach them quickly from anywhere. This “well-connectedness” is what makes expander graphs so powerful for quantum codes: errors cannot hide in small corners because the checks surrounding them will always detect something.
Expander graphs have several crucial properties: 1. Rapid mixing: Random walks converge quickly to uniform distribution 2. Small diameter: Any two vertices are connected by short paths 3. Boundary expansion: Any subset has many neighbors outside
For quantum Tanner codes, property (3) is essential: errors cannot “hide” in small subsets because the check nodes detect them quickly.
7.8 Example: Cayley Graph Expanders
A classic example is the Cayley graph of “SL”(2, q) or \(Z_2^k\): - Vertices: group elements - Edges: multiplication by generators
These graphs have excellent expansion properties and have been used in several quantum Tanner code constructions.
The existence of expander graphs was proven probabilistically. For any \(d ≥ 3\), random \(d\)-regular graphs are expanders with high probability. Explicit constructions exist but are more complex.
7.8.1 Distance Amplification
The quantum Tanner construction can achieve better distance than hypergraph product.
If the base codes have good distance properties and the graph has sufficient expansion, the quantum Tanner code can achieve: - Distance growing with \(n\) for constant rate - Good minimum distance
This requires careful design of the base codes and graph.
The quantum Tanner code construction is more flexible than hypergraph product because it doesn’t require the specific tensor structure. This flexibility enables better distance properties.
7.9 Significance of “Good” qLDPC Codes
The breakthrough in “good” quantum LDPC codes resolves a decades-old open problem.
7.9.1 Historical Background
The quantum Singleton bound gives a fundamental limit.
For any \([[n, k, d]]\) quantum code: $ n - k ≥ 2(d - 1) $
Equivalently: \(R ≤ 1 - 2/d\) for rate \(R = k/n\).
This is weaker than the classical Singleton bound \(R ≤ 1 - d/n\).
A family of quantum codes is “good” if: - Rate \(R = k/n\) is bounded away from zero as \(n → ∞\) - Distance \(d = Ω(n)\) (grows linearly with \(n\))
This matches the classical Gilbert-Varshamov bound achievability.
For decades, the best known qLDPC codes had \(d = O(√{n})\) or \(d = O(1)\). A “good” qLDPC code was an open problem.
7.9.2 The Hastings-Haah-O’Donnell Breakthrough
In 2021, Hastings, Haah, and O’Donnell @hastings2021 achieved a breakthrough.
There exist families of quantum LDPC codes with: - Constant rate \(R > 0\) - Distance \(d = Ω(n^δ)\) for some \(δ > 0\)
These are the first “good” quantum LDPC codes.
The construction uses product of chains and is probabilistic. Subsequent work improved the distance to \(Ω(n)\) @panteleev2023.
7.10 Example: Good qLDPC Parameters
The Hastings-Haah-O’Donnell codes achieve: - \(R = 0.001\) (rate ~0.1%) - \(d = Ω(n^{0.1})\) - Local check weight: 24
Follow-up constructions achieve \(R ≈ 0.1\%\) with \(d = Ω(n^{0.8})\) @panteleev2023.
7.10.1 Improved Constructions: 2023-2025 Breakthroughs
The 2022-2025 period saw dramatic improvements in qLDPC constructions, achieving both constant rate AND linear distance.
Panteleev-Kalachev (2022-2023) achieved the first asymptotic construction with constant rate \(Ω(1/log n)\) and linear distance \(Ω(n)\) @panteleev2023. Their decoder runs in almost-linear time, making these codes practical.
The Panteleev-Kalachev construction uses: 1. A classical Tanner code with good distance 2. A random lift of a base graph 3. Careful analysis of the resulting quantum code parameters
Key insight: Using lifted covers of graphs amplifies distance while maintaining the sparse structure needed for efficient decoding.
The Panteleev-Kalachev codes achieve: - Rate \(R = Ω(1/log n)\) (logarithmic in code size) - Distance \(d = Ω(n)\) (linear in code size) - Check weight \(O(log n)\) (polylogarithmic) - Decoding complexity \(O(n log n)\) (almost-linear)
These are the first “asymptotically good” quantum codes with practical decoders.
Dinur et al. (2023) developed locally testable quantum codes with improved distance and local testability properties @dinur2023. These constructions further optimize the trade-off between rate and distance.
Recent advances (2024-2025) have achieved explicit constructions with: - Constant rate \(O(1)\) and linear distance \(Ω(n)\) @baird2025 - Bounded check degree enabling efficient decoding @huang2025 - Hardware-efficient designs compatible with superconducting qubits @liu2024
While theoretical constructions have improved dramatically, practical deployment requires addressing additional challenges: - Syndrome extraction with long-range connectivity - Decoder implementation complexity - Fault-tolerant gate sets
Current research focuses on bridging the gap between asymptotic excellence and practical implementability.
7.10.2 Improved Constructions
Subsequent work has improved the parameters significantly.
| Construction | Year | Rate | Distance |
|---|---|---|---|
| Hastings-Haah-O’Donnell | 2021 | \(O(1/n)\) | \(Ω(n^{0.1})\) |
| Panteleev-Kalachev | 2022 | \(Ω(1/log n)\) | \(Ω(n)\) |
| Haah-Hastings @haah2022 | 2023 | \(O(1)\) | \(Ω(n)\) |
| Present best | 2024 | \(O(1)\) | \(Ω(n)\) |
The 2022-2023 constructions achieve both constant rate AND linear distance: \(k = Θ(n)\) and \(d = Θ(n)\).
This is the quantum analogue of classical “good” codes.
7.10.3 Impact on Fault-Tolerant Quantum Computation
Good qLDPC codes dramatically reduce the overhead for fault-tolerant quantum computation.
For a surface code with rate \(k/n = 1/n\) (planar code encodes 1 qubit): - Overhead scales as \(O(n^2)\) for distance \(n\)
For a good qLDPC code with rate \(R = O(1)\): - Overhead scales as \(O(n)\) for distance \(n\)
Reduction by factor of \(O(n)\) in qubit overhead.
7.11 Example: Overhead Comparison
Target logical error rate \(p_L = 10^{-12}\) at physical error rate \(p = 10^{-3}\): - Surface code: ~10,000 physical qubits per logical qubit - Good qLDPC: ~1,000 physical qubits per logical qubit
For 1,000 logical qubits (needed for useful algorithms): - Surface code: ~10 million physical qubits - Good qLDPC: ~1 million physical qubits
Factor of 10 reduction, enabling more practical quantum computers.
7.11.1 Decoding Challenges for qLDPC Codes
Good parameters are only half the battle — efficient decoding is equally important.
Why BP struggles on qLDPC codes. Classical belief propagation works well on codes with large girth (no short cycles). Quantum LDPC codes, especially good ones, have many short cycles due to their dense but sparse structure. This causes BP to oscillate or converge to incorrect solutions.
7.11.2 Small-Set Flip Decoding
One promising approach for qLDPC decoding is small-set flip decoding.
Given a syndrome and decoding iteration: 1. Identify a small set of qubits (e.g., 3-5) that could explain the syndrome 2. Flip errors on this set and compute the new syndrome 3. Accept the flip if the syndrome weight decreases 4. Repeat until syndrome is empty or maximum iterations reached
This approach explores small error configurations exhaustively, handling degeneracy better than pure BP.
7.11.3 BP+OSD for Quantum Codes
Another approach combines belief propagation with ordered statistics decoding.
BP+OSD decoding for quantum codes: 1. Run BP for a fixed number of iterations 2. If BP fails to converge, use the posterior LLRs to rank error candidates 3. Systematically test the most likely \(k\)-error patterns (OSD order \(k\)) 4. Return the pattern that produces the correct syndrome
This handles the short cycles that cause pure BP to fail.
The trade-off: higher OSD order improves accuracy but increases decoding time exponentially.
7.11.4 Current Decoding State of the Art
| Decoder | Complexity | Threshold | Status |
|---|---|---|---|
| MWPM | \(O(n^3)\) | ~10% surface code | Incompatible with general qLDPC |
| Union-Find | \(O(n log n)\) | ~10% surface code | Incompatible with general qLDPC |
| BP | \(O(n "iterations")\) | ~5% qLDPC | Struggles with degeneracy |
| BP+OSD (k=10) | \(O(n binom(n, k))\) | ~8% qLDPC | Promising, slow |
| Small-Set Flip | \(O(n^k)\) | ~7% qLDPC | Active research |
Decoding qLDPC codes is like solving a puzzle where the picture (syndrome) doesn’t uniquely determine the pieces (errors) because many different error patterns produce the same syndrome. Good qLDPC codes have even more ambiguity (degeneracy) than surface codes, making standard decoding algorithms struggle. The solution is to explore multiple possibilities systematically — like trying different puzzle piece combinations until the picture makes sense.
7.11.5 Open Problems
Despite the breakthrough, significant challenges remain.
Current good qLDPC codes have limitations: 1. Decoder complexity: MWPM doesn’t apply directly, BP has challenges 2. Circuit-level noise: Syndrome extraction requires long-range gates 3. Concrete constructions: Only probabilistic constructions known
Research directions: - Explicit constructions with efficient decoding - Local implementations compatible with 2D hardware - Fault-tolerant gate implementations
The surface code remains practical despite lower rate because of its locality and efficient decoding.
7.12 Key Takeaways
- CSS constraint: Quantum LDPC codes require \(H_X H_Z^T = 0\), coupling X and Z check matrices — unlike classical LDPC where checks are independent
- Hypergraph product: Systematically constructs quantum codes from classical codes via \(H_X = H ⊗ I\) and \(H_Z = I ⊗ H\), automatically satisfying the CSS condition
- Distance limitation: Early hypergraph product constructions achieved constant rate but \(O(1)\) distance, motivating the search for better constructions
- Quantum Tanner codes: Use two Tanner codes with \(C_Z ⊂ C_X\) to achieve better distance, with parameters \([[n, k_X - k_Z, min(d_X, d_Z^⊥)]]\)
- Good qLDPC codes: 2021-2023 breakthroughs achieved families with both constant rate \(R > 0\) AND linear distance \(d = Ω(n)\) — resolving a decades-old open problem
- Decoding challenges: BP struggles on qLDPC due to short cycles and degeneracy; BP+OSD and small-set flip decoding are promising alternatives
- Overhead reduction: Good qLDPC codes reduce qubit overhead by factor of \(O(n)\) compared to surface codes, crucial for large-scale quantum computation
7.13 Bridge to Chapter 6
We have seen that quantum LDPC codes offer excellent asymptotic properties but present decoding challenges. Chapter 6 examines these decoding algorithms in depth, starting with minimum weight perfect matching for surface codes and progressing to belief propagation, Union-Find, and modern variants like BP+OSD. The theme is the trade-off between decoding accuracy and computational complexity — a central concern for practical quantum error correction.
We will also examine neural network decoders in Chapter 7, which offer a data-driven approach to handling the degeneracy and short cycles that plague traditional decoders on qLDPC codes.
7.14 Exercises
Quantum LDPC Parameters. Consider a quantum LDPC code family. (Level: basic)
What does it mean for a qLDPC code to have “constant rate”? Why is this desirable compared to the surface code?
If a \([[n, k, d]]\) code has \(k = Theta(n)\) and \(d = Theta(n)\), what can you say about the number of physical qubits needed per logical qubit as \(n -> infinity\)?
The surface code has \(k = O(1)\) and \(d = O(sqrt(n))\). Compare its asymptotic efficiency to a good qLDPC code.
Hypergraph Product Construction. The hypergraph product takes two classical codes \(C_1\) and \(C_2\) to produce a quantum code. (Level: intermediate)
If \(C_1\) is an \([n_1, k_1, d_1]\) code and \(C_2\) is an \([n_2, k_2, d_2]\) code, what are the parameters of the resulting quantum code?
Why does the hypergraph product naturally produce a CSS code?
What property must \(C_1\) and \(C_2\) have for the resulting quantum code to be LDPC?
Tanner Code Structure. Consider a Tanner code constructed from a base graph \(G\) and local code \(C_0\). (Level: intermediate)
Explain how the vertices and edges of \(G\) relate to the bits and constraints of the Tanner code.
If \(G\) is a \((d_v, d_c)\)-regular bipartite graph and \(C_0\) is a \([d_c, k_0, d_0]\) code, what is the rate of the resulting Tanner code?
Why do expander graphs lead to Tanner codes with good distance properties?
Good Code Trade-offs. Compare different quantum code families. (Level: basic)
Surface code: rate \(k/n approx 1/n\), distance \(d = O(sqrt(n))\). Explain why this is not “good.”
Hypergraph product from random LDPC: rate \(k/n = O(1)\), distance \(d = O(1)\). Explain why this is also not “good.”
Good qLDPC (Panteleev-Kalachev): rate \(k/n = Omega(1/log n)\), distance \(d = Omega(n)\). Why does this qualify as “good”?
What practical advantages do surface codes retain despite not being asymptotically good?
CSS Construction. Consider constructing a CSS code from two classical codes. (Level: intermediate)
Given classical codes \(C_1\) and \(C_2\) with parameters \([n_1, k_1, d_1]\) and \([n_2, k_2, d_2]\), what conditions must hold for a valid CSS code?
If \(C_2 ⊂ C_1\) and both have length \(n\), prove that the resulting CSS code has \(k = k_1 - k_2\) logical qubits.
Show that the Steane code \([[7,1,3]]\) can be constructed from the \([7,4,3]\) Hamming code and its dual.
Explain why simply taking any two classical codes does not generally yield a valid quantum code.
Decoding qLDPC Codes. Explain the challenges in decoding quantum LDPC codes. (Level: intermediate)
Why does minimum weight perfect matching (MWPM) work well for surface codes but not for general qLDPC codes?
What property of qLDPC codes causes belief propagation to fail or oscillate?
How does BP+OSD address the limitations of pure BP? What is the trade-off?
Why is degeneracy both an advantage and a challenge for quantum decoding?
Hypergraph Product Implementation. Implement the hypergraph product construction in code. (Level: advanced)
Write a function that takes a classical parity-check matrix \(H\) and returns the X-type and Z-type check matrices for the hypergraph product.
Use your implementation with the \([7,4,3]\) Hamming code. Verify the resulting code parameters are \([[49, 7, 3]]\).
Compute the rate of the hypergraph product code as a function of the classical code rate. Does the quantum code rate improve or degrade?
Test your code with a \([15,11,3]\) Hamming code. What are the resulting quantum parameters?
Expander Graphs and Distance. Analyze why expander graphs lead to good quantum codes. (Level: challenge)
Define the isoperimetric number (expansion factor) of a graph. How does it relate to code distance?
Show that a complete graph on \(n\) vertices has perfect expansion. What is its isoperimetric number?
Consider a quantum Tanner code built on an expander graph. Prove that the distance grows with the expansion factor.
If a \((3, 6)\)-regular expander has expansion \(epsilon = 0.01\), estimate the distance of the resulting quantum Tanner code as a function of \(n\). What is the asymptotic scaling?