Lesson 03 - CSS Codes, Tanner Graphs, LDPC, and Locality¶

Prerequisites And Diagnostic Checks¶

Before teaching, ask:

What does \(C^\perp\) mean?
Why does \(H_XH_Z^T=0\) imply commutation of CSS checks?
Given a parity-check matrix, can you draw variable nodes and check nodes?

The first two questions determine whether to slow down the CSS bridge.

Concrete Motivation From The Research Map¶

Conjecture 3 cares about syndrome-extraction depth. Syndrome extraction does not measure an abstract code; it measures specific checks. Those checks are rows of \(H_X\) and \(H_Z\). The Tanner graph records exactly which qubits each check touches.

That is why this lesson moves from algebra to graph structure.

Classical Codes Inside CSS Codes¶

A CSS code is built from two binary classical codes satisfying an orthogonality condition. One standard convention is to choose parity-check matrices \(H_X\) and \(H_Z\) with

\[ H_XH_Z^T=0. \]

Each row of \(H_X\) gives an X-type stabilizer. Each row of \(H_Z\) gives a Z-type stabilizer. The dot product of an X-row and a Z-row counts their overlap modulo \(2\). If the overlap is even, the Pauli operators commute.

This is the stabilizer formalism in GF(2) clothing.

A Warning About CSS Distance¶

It is tempting to say "the CSS distance is just the distance of the two classical codes." That is too loose.

The correct object is relative distance modulo the stabilizer subspace. X-logicals are nontrivial representatives in a quotient such as

\[ C_X/C_Z^\perp, \]

depending on convention. Z-logicals are the analogous quotient on the other side. The quantum distance is the minimum weight of a nontrivial logical representative, not the minimum weight of an arbitrary vector in one classical code.

This distinction matters later because changing a generating set can change a Tanner presentation without changing the stabilizer space.

Tanner Graphs From Matrices¶

Given a parity-check matrix \(H\), its Tanner graph is bipartite:

variable nodes correspond to columns
check nodes correspond to rows
an edge connects check \(i\) to variable \(j\) when \(H_{ij}=1\)

For the Hamming matrix from Lesson 01, row one touches variables \(1,3,5,7\). In the Tanner graph, that row is a check node connected to those four variable nodes.

The graph and matrix contain the same incidence information, but they emphasize different questions:

matrix view: linear algebra, rank, null space, duality
graph view: degree, local neighborhoods, expansion, routing

Conjecture 3 lives mostly in the graph view, but it never stops depending on the matrix view.

Degree Constraints And LDPC¶

The degree of a variable node is the number of checks touching that coordinate. The degree of a check node is the number of variables in that check.

A classical LDPC code has row weights and column weights bounded by constants independent of \(n\). A quantum LDPC code has bounded check weights and bounded qubit participation for both X and Z checks.

This bounded-degree condition is a locality condition, but not a geometric locality condition. A check of weight \(6\) is locally small in algebraic support, but its six qubits could be far apart on a chip.

This distinction is central:

LDPC says each check touches only constantly many qubits
2D hardware locality says those qubits must be physically near to interact cheaply

QLDPC codes satisfy the first condition. Conjecture 3 is about the cost of failing the second.

Worked Example: A Tanner Graph As A Guest Graph¶

Take a parity-check matrix with three checks and seven variables. The Tanner graph tells you which data qubits each syndrome ancilla must interact with.

If you place the seven data qubits on a line or grid, each Tanner edge becomes a demand for physical interaction. Some interactions may be native. Others must be routed through SWAPs or other compilation resources.

This is the first appearance of the guest-host distinction:

the Tanner graph is the guest demand
the hardware graph is the host supply

Conjecture Linkage¶

The local research graph uses Tanner expansion and cut arguments. Those words only make sense once \(H\) has become a graph. Later, expansion will say that many small or balanced sets of variable nodes have many neighboring checks. Hardware cuts will say that the physical machine cannot service all those cross-cut demands quickly.

What This Does And Does Not Prove¶

LDPC does not imply good distance. A sparse graph can still have terrible expansion. Likewise, a good abstract code may have a bad parity-check presentation for hardware purposes.

This lesson only defines the sparse graph language. Expansion comes next.

Active Recall¶

Translate \(H_XH_Z^T=0\) into the even-overlap rule.
Draw the Tanner graph of a small parity-check matrix.
What is the difference between bounded check weight and geometric locality?
Why is the Tanner graph the "guest" in the guest-host picture?

Next-Step Handoff¶

Next we study the local shape of Tanner graphs: girth, neighborhoods, Tanner codes, and small-set expansion.