Skip to content

Lesson 04 - Girth, Local Views, Tanner Codes, and Small-Set Expansion

Prerequisites And Diagnostic Checks

Ask:

  1. What is a cycle in a Tanner graph?
  2. What does a check node enforce on its neighboring variables?
  3. Why might local neighborhoods be easier to analyze than a whole code?

Concrete Motivation From The Research Map

The Conjecture 3 route needs local-expander QLDPC families. That phrase hides several ideas:

  • local constraints are small
  • local neighborhoods have useful structure
  • small sets cannot hide from checks
  • this forces cross-cut syndrome demand

This lesson builds those ideas carefully.

Girth And Local Tree Structure

The girth of a graph is the length of its shortest cycle. In a bipartite Tanner graph, all cycles have even length, so a \(4\)-cycle is the shortest possible problem cycle.

If a graph has girth \(g\), then the radius-\(r\) neighborhood of a vertex is a tree whenever \(2r+1<g\). This is useful because tree-like neighborhoods avoid short feedback loops in message-passing decoders.

Be cautious about a common overstatement: spectral expansion and girth are related in some explicit constructions, but a large spectral gap alone does not guarantee large girth. Expanders can have short cycles. Girth is a local cycle property; spectral expansion is a global bottleneck property.

Local Views And Neighborhoods

The radius-\(r\) neighborhood \(\mathcal N_r(v)\) is the subgraph visible from \(v\) within graph distance \(r\).

For LDPC codes, local views matter because each check only sees constantly many variables. A huge code can therefore be assembled from many small local constraints.

This is also where puncturing and shortening reappear. A local view is often a restriction or projection of global code data onto a small coordinate set.

Tanner Code Construction

A Tanner code starts with:

  • a regular graph or bipartite constraint graph
  • a small local code \(C_0\)
  • a rule that every local neighborhood must look like a word in \(C_0\)

One common schematic form is:

\[ T(G,C_0)=\{x : x|_{\mathcal N(v)}\in C_0\text{ for every constraint vertex }v\}. \]

The exact placement of bits depends on the Tanner-code convention. The core idea is stable: a global code is built by gluing many overlapping local code constraints along a graph.

Worked Example Before Abstraction

Imagine each check node has degree \(4\), and the local code \(C_0\) is the even-parity code of length \(4\).

Then every check says: "the four incident edge or variable bits must have even parity." A global word is valid only if all local checks pass simultaneously.

If the underlying graph has poor connectivity, an error can stay hidden in a small region. If the graph expands, a small corrupted region touches many checks. That is the local-to-global mechanism.

Small-Set Expansion

Small-set expansion says that small sets have many neighbors. A typical form is:

\[ \lvert\mathcal N(S)\rvert\ge \alpha \lvert S\rvert \]

for every variable set \(S\) up to some size threshold.

For coding, the stronger useful versions often count unique neighbors or boundary checks, not just all neighbors. The reason is simple: if every small nonzero support triggers many checks, then no low-weight nonzero word can pass all checks.

So the proof shape is contrapositive:

  1. suppose there is a low-weight nonzero codeword
  2. look at its support \(S\)
  3. expansion says \(S\) has too many exposed checks
  4. those checks cannot all be satisfied
  5. contradiction

This is how expansion becomes distance.

The Anchor Gap

The local research graph distinguishes several expansion layers. Quantum Tanner codes have strong expansion properties in auxiliary diagonal graphs. The Conjecture 3 lower-bound route wants expansion for the stabilizer-presentation Tanner graph or an invariant substitute.

That transfer is not a harmless formatting issue. It is one of the mathematical steps that must be justified.

Relevant nodes:

What This Does And Does Not Prove

This lesson explains why expansion can imply distance for Tanner-style codes. It does not prove that every good QLDPC code has the exact small-set expansion needed for every lower-bound theorem. It also does not prove the quantum Tanner transfer by itself.

Active Recall

  • Why does large girth make small neighborhoods tree-like?
  • Why is "spectral expansion implies large girth" too strong as a general claim?
  • Explain the Tanner code construction in one sentence.
  • Why does unique-neighbor expansion help prove distance?
  • What is the anchor gap?

Next-Step Handoff

Next we learn the spectral side of expansion: adjacency matrices, eigenvalues, the spectral gap, and the Petersen graph as a small concrete expander.