Skip to content

Expander Graphs and Graph Cuts

Prerequisites And Diagnostic Checks

You can treat this chapter as covered if you can:

  • explain spectral gap for a regular graph
  • define edge expansion or bisection width
  • compute the 2D grid bottleneck at the level of Theta(sqrt(N))
  • explain why expanders have large balanced cuts

Concrete Motivation

Good QLDPC codes need connectivity that behaves like an expander. Static 2D hardware behaves like a grid. The central conflict is not that the grid is inconvenient; it is that its balanced cuts are too small.

Worked Example Before Abstraction

Compare two graphs:

  • an expander on n vertices, where every balanced cut has Theta(n) crossing edges
  • a near-square 2D grid on N vertices, where a vertical balanced cut has only Theta(sqrt(N)) crossing edges

If N=Theta(n), then code demand is linear but hardware capacity per layer is only square-root.

Formal Takeaway

Bisection width measures the minimum number of edges crossing a balanced cut. Expansion lower-bounds this quantity for the guest graph, while planar or grid geometry upper-bounds it for the host graph.

This is the simple version of the Conjecture 3 lower-bound intuition:

depth >= guest cross-cut demand / host cross-cut service capacity.

The local research graph sharpens this into nodes such as:

What This Does And Does Not Prove

This chapter explains the geometric mechanism. It does not yet identify the exact stabilizer-space demand, nor does it prove that a full compiler-native CD(T_n,G) functional captures every allowed compilation map.

Active Recall

  • Why does an expander have large bisection width?
  • Why does a square grid have only Theta(sqrt(N)) bisection width?
  • Where does the Omega(sqrt(n)) depth intuition come from?

Next-Step Handoff

Now return to quantum codes: which QLDPC constructions actually achieve good parameters and create this expansion demand?