Lesson 06 - Expansion, Cuts, Ramanujan Graphs, and 2D Grids¶
Prerequisites And Diagnostic Checks¶
Ask:
- What is the spectral gap of a \(d\)-regular graph?
- What does it mean for a set of vertices to have many boundary edges?
- Why would a 2D grid have a small balanced cut?
Concrete Motivation From The Research Map¶
This lesson is the geometric core of Conjecture 3. Good QLDPC codes want expansion. Static 2D hardware has small separators. The lower-bound mechanism is the collision between those two facts.
Edge Expansion And Cheeger¶
For a graph \(G\), the edge boundary of a set \(S\) is the set of edges crossing from \(S\) to its complement. The edge expansion can be written as
For a \(d\)-regular graph, Cheeger-type inequalities relate \(h(G)\) to the spectral gap. Up to convention-dependent constants, a constant spectral gap gives constant edge expansion.
A useful unnormalized form is:
The exact constants are less important here than the bridge:
spectral gap -> no cheap combinatorial cuts.
Ramanujan Graphs¶
An infinite family of \(d\)-regular graphs cannot have arbitrary spectral gap. The Alon-Boppana phenomenon says the best possible nontrivial eigenvalue scale is about \(2\sqrt{d-1}\).
Ramanujan graphs meet this optimum:
They are optimal constant-degree expanders. Quantum Tanner constructions use Ramanujan/Cayley expansion because they need strong connectivity without growing degree.
Bisection Width¶
Bisection width asks how many edges must be cut to split a graph into two large pieces.
Examples:
- a path has bisection width \(1\)
- a cycle has bisection width \(2\)
- a constant-degree expander has bisection width \(\Theta(n)\)
- a near-square 2D grid with \(N\) vertices has bisection width \(\Theta(\sqrt N)\)
This is the first direct guest-host comparison:
- expander guest demand across a balanced cut is linear
- 2D host capacity across a balanced cut is only square-root scale
The 2D Grid Bottleneck¶
For a rectangular grid \(P_a\times P_b\) with \(a\le b\), the bisection width is exactly \(a\). For a near-square grid, \(a=\Theta(\sqrt N)\).
The local node 2d-grid-bisection-width.md records this as a host-capacity statement. It is not yet a syndrome-depth theorem by itself. It becomes a depth theorem only after you prove that the code creates enough cross-cut demand.
The planar separator theorem says this is not just a quirk of perfect grids. Planar graphs have balanced separators of size \(O(\sqrt N)\), so 2D hardware broadly inherits this bottleneck.
Routing Tightness¶
The grid routing number is also \(\Theta(\sqrt N)\) for near-square grids. This tells you the scale is real: the lower bound matches the natural time needed for generic routing on such hardware.
But routing number is about token permutations. Syndrome extraction is a stabilizer-measurement task, so routing tightness is supporting intuition rather than the full proof.
The Expansion Mismatch¶
Assume a code-side object creates \(\Omega(n)\) cross-cut syndrome demand. Assume a near-square 2D hardware cut can service only \(O(\sqrt N)\) cross-cut interactions per layer.
Then depth must be at least
When \(N=\Theta(n)\), this becomes
This is the static 2D barrier.
The local node expansion-cut-to-syndrome-depth.md states the more invariant form:
What This Does And Does Not Prove¶
This lesson explains the geometry. It does not prove that a given quantum code produces the required cross-cut stabilizer demand. That is a code-side theorem. It also does not settle the full original CD(T_n,G) conjecture, whose compiler-native semantics are subtler.
Active Recall¶
- What does Cheeger connect?
- Why are Ramanujan graphs optimal for fixed degree?
- Why does a 2D grid have bisection width \(\Theta(\sqrt N)\)?
- Derive the informal ratio \(n/\sqrt N\).
- What extra statement is needed beyond grid bisection width?
Next-Step Handoff¶
Next we enter QLDPC constructions: CSS logical operators, asymptotically good parameters, left-right Cayley complexes, quantum Tanner codes, and the anchor gap.