Skip to content

Lesson 05 - CSS Tanner Graphs, Spectra, and the Petersen Graph

Prerequisites And Diagnostic Checks

Ask:

  1. Why does a CSS code have two Tanner graphs?
  2. What does an eigenvalue of an adjacency matrix measure informally?
  3. What would a graph bottleneck look like in a random walk?

Concrete Motivation From The Research Map

Quantum Tanner codes use expander graphs as scaffolding. To read the research map, you need two complementary languages for expansion:

  • combinatorial expansion: how many edges or neighbors leave a set
  • spectral expansion: what eigenvalues say about bottlenecks

This lesson connects CSS Tanner graphs to spectral graph intuition.

Tanner Graph Of A CSS Code

A CSS code has two parity-check matrices:

  • \(H_X\) for X-type checks
  • \(H_Z\) for Z-type checks

So it has two Tanner graphs:

  • \(T_X\), connecting X-checks to qubits
  • \(T_Z\), connecting Z-checks to qubits

The two graphs share the same qubit nodes. The commutativity condition

\[ H_XH_Z^T=0 \]

means every X-check and Z-check overlap on an even number of qubits.

Graphically: every X-check node and Z-check node have even common neighborhood size.

Why CSS Tanner Graphs Are Not Just Two Classical Graphs

The two graphs are coupled by commutativity. You cannot choose a good X-side LDPC code and a good Z-side LDPC code independently and expect a CSS code. Their overlap pattern must satisfy the even-overlap rule.

Quantum Tanner codes solve this by building both sides from a common algebraic complex. The commutativity is built into the construction rather than patched in later.

Adjacency Spectra Of Regular Graphs

For a graph \(G\), the adjacency matrix \(A\) has entries

\[ A_{ij}=1 \]

when vertices \(i\) and \(j\) are adjacent, and \(0\) otherwise.

If \(G\) is \(d\)-regular, then the all-ones vector is an eigenvector with eigenvalue \(d\). For a connected \(d\)-regular graph, this is the largest eigenvalue.

The important quantity is the nontrivial spectrum. A common spectral gap is

\[ \gamma=d-\lambda_2, \]

where \(\lambda_2\) is the second-largest eigenvalue for a non-bipartite connected graph. More generally, one tracks the largest nontrivial eigenvalue in absolute value.

Large spectral gap means the graph has no easy bottleneck. Random walks mix quickly, and sets cannot be too isolated.

Worked Contrast: Path Versus Complete Graph

A long path has an obvious bottleneck. Cut one middle edge and the graph splits into two large pieces. Its spectral gap shrinks with size.

A complete graph has no narrow bottleneck. Every vertex talks to every other vertex. Its spectral gap is huge, but its degree is also huge, so it is useless as an LDPC scaffold.

Expanders aim for the best of both:

  • constant degree
  • no large bottlenecks
  • spectral gap bounded below by a constant

The Petersen Graph As A Small Expander

The Petersen graph has \(10\) vertices and degree \(3\). Its nontrivial eigenvalues include \(1\) and \(-2\), so the usual non-bipartite gap \(3-1=2\) is large.

It is a good teaching object because it is small enough to draw but connected enough that small sets are hard to isolate.

Do not overinterpret the example. The Petersen graph is not a code family. It is a finite model for the kind of bottleneck-free behavior that expander families maintain as \(n\) grows.

Conjecture Linkage

The quantum Tanner construction uses diagonal graphs with controlled spectral expansion. The local node quantum-tanner-diagonal-expansion-structure.md records the relevant theorem-level statement:

\[ \lambda(G^\square_0),\lambda(G^\square_1)\le 4\Delta. \]

That is an auxiliary spectral-expansion anchor. Later we must still ask how it transfers to the stabilizer-presentation object that syndrome extraction sees.

What This Does And Does Not Prove

Spectral expansion supports combinatorial expansion, but the exact property needed depends on the theorem. In particular, spectral expansion of an auxiliary graph is not automatically small-set expansion of a chosen quantum stabilizer Tanner graph.

Active Recall

  • What is the even-overlap rule for CSS Tanner graphs?
  • Why is high degree not an acceptable way to get connectivity for LDPC codes?
  • What does a large spectral gap rule out?
  • Why is the Petersen graph only an intuition-building example?

Next-Step Handoff

Next we turn spectral expansion into cut language: Cheeger inequalities, Ramanujan graphs, bisection width, planar separators, and the 2D grid bottleneck.