CSS and QLDPC Codes

Prerequisites And Diagnostic Checks

Before teaching this chapter live, ask:

• What does H_XH_Z^T=0 mean physically?
• What is a logical operator in stabilizer language?
• What does d measure in a quantum code?
• What does bounded check weight buy us physically?

Concrete Motivation

Your surface-code intuition says local stabilizers are easy to measure on a 2D chip. QLDPC codes ask for much better logical density and distance, but the checks no longer sit naturally on the hardware geometry. This chapter explains the code side of that trade.

Worked Example Before Abstraction: The [[4,2,2]] CSS Code

Use the even-parity check on four qubits for both X and Z:

• H_X = [1 1 1 1]
• H_Z = [1 1 1 1]

The commutativity check is H_XH_Z^T = 1+1+1+1 = 0 over GF(2).

The X-type logical operators are not arbitrary even-weight X strings. They are the nontrivial representatives in the quotient C_X / C_Z^\perp. The stabilizer XXXX is trivial on the code space, but XXII, XIXI, and related weight-2 representatives act nontrivially.

That is why this code has distance 2: the minimum nontrivial logical weight is 2.

Formal Definitions

For a CSS code built from classical codes C_X and C_Z satisfying C_Z^\perp subset C_X:

• X-logicals live in C_X / C_Z^\perp
• Z-logicals live in C_Z / C_X^\perp
• distance is the minimum weight of a nontrivial representative on either side
• a QLDPC family has bounded check and qubit degree
• an asymptotically good QLDPC family has k=Theta(n) and d=Theta(n) while staying LDPC

Why Expansion Enters

Linear distance means small error supports should not hide from checks. In Tanner-graph language, small variable sets need enough neighboring checks to expose them. This is the code-side reason expansion appears.

For Conjecture 3, this is the key tension:

• expansion is good for distance
• bounded degree is good for local check complexity
• expansion plus bounded degree is bad for static 2D routing

Quantum Tanner Codes

Quantum Tanner codes are the anchor family for this course because they give theorem-level asymptotically good QLDPC codes.

At the level needed here:

• start with a left-right Cayley complex
• build two diagonal graphs, G_0^square and G_1^square
• define classical Tanner codes C_0 = T(G_0^square, C_A^\perp) and C_1 = T(G_1^square, C_B^\perp)
• assemble the CSS pair from C_0 and C_1
• use component-code hypotheses to obtain k,d=Theta(n)

The local graph currently records this in:

• quantum-tanner-expander-anchor.md
• quantum-tanner-diagonal-expansion-structure.md

The Anchor Gap

The construction has strong diagonal-graph expansion. The Conjecture 3 route needs expansion of the relevant stabilizer-presentation Tanner graph or an invariant replacement for it.

The graph has narrowed this gap through incidence expansion, local generator blowups, and parity-Tanner expansion nodes, but the teaching point is simpler: expansion exists at several layers, and the proof must move it to the layer that controls syndrome extraction.

Other QLDPC Families

For orientation:

• hypergraph product codes are QLDPC and high-rate in useful regimes, but their distance is not linear
• fiber bundle codes improved the distance landscape
• Panteleev-Kalachev and Leverrier-Zemor mark the modern asymptotically good QLDPC breakthrough
• quantum Tanner codes are especially useful here because their expansion structure is explicit enough to connect to Conjecture 3

What This Does And Does Not Prove

This chapter explains why good QLDPC codes are the right guest objects. It does not itself prove the syndrome-depth lower bound. That requires the hardware/service side taught next.

Active Recall

• Explain C_X / C_Z^\perp without using the word "quotient" first.
• Why does d=Theta(n) push us toward expansion?
• What makes a QLDPC code both physically attractive and geometrically difficult?
• What is the anchor gap in the quantum Tanner route?

Next-Step Handoff

Move from code construction to circuit realization: how does one measure these checks on hardware that only allows local gates?