Lesson 02 - Static 2D Theorem and Separator Meta-Theorem

Goal

Understand the theorem-backed static hardware result: good stabilizer codes, and in particular theorem-level Quantum Tanner families, require large depth for local syndrome extraction on static 2D hardware with only linear space.

Prerequisites And Diagnostic Checks

1. What are the parameters \([n,k,d]\)?
2. Why does \(k=\Theta(n)\) and \(d=\Theta(n)\) define a good quantum code family?
3. What is a near-square 2D local architecture?
4. Why does allowing free classical computation not remove a quantum locality lower bound?

Concrete Motivation

The foundations course taught the bisection-width picture: expanders have large cuts, grids have small cuts. This lesson adds the theorem that bypasses many presentation worries.

The decisive node is 2d-syndrome-depth-from-code-parameters.md. It packages a 2D local syndrome-extraction lower bound directly from code parameters.

For a good code family:

\[ k=\Theta(n),\qquad d=\Theta(n). \]

If a 2D local syndrome-extraction circuit uses \(m=\Theta(n)\) qubits total, the lower bound becomes:

\[ \Delta=\Omega(\sqrt n). \]

This is why the minimal static 2D theorem is no longer the main open gap.

Worked Example Before Abstraction

Take a hypothetical good QLDPC family with \(n\) data qubits, \(k=cn\), and \(d=c'n\) for constants \(c,c'>0\). Put it on a 2D grid with \(m=Cn\) total qubits including ancillas.

The theorem gives:

\[ \Delta=\Omega\left(\frac{k\sqrt d}{m}\right). \]

Substitute the parameters:

\[ \Delta =\Omega\left(\frac{n\sqrt n}{n}\right) =\Omega(\sqrt n). \]

Notice what did not enter:

• no chosen Tanner graph;
• no chosen stabilizer generating set;
• no detailed SWAP route;
• no claim about individual checks crossing a particular cut.

That makes this route presentation-invariant for theorem-level good families.

Formal Theorem Layer

The local graph uses these nodes:

• 2d-syndrome-depth-from-code-parameters.md
• quantum-tanner-good-family-presentation-invariant-2d-barrier.md
• static-2d-separator-cut-rank-manuscript-package.md

The theorem-level route is:

1. Quantum Tanner families certified by the relevant good-code theorem have \(k,d=\Theta(n)\).
2. The 2D syndrome-depth theorem gives \(\Omega(k\sqrt d/m)\) depth.
3. With linear total qubits \(m=\Theta(n)\), the depth is \(\Omega(\sqrt n)\).

This is the cleanest route for the minimal static near-square 2D theorem.

Separator Meta-Theorem

The square grid is not the only hardware family with separators. The node weighted-separator-function-to-syndrome-depth.md packages a broader principle:

if the hardware has sublinear weighted separators and the code has local-expander demand, then syndrome extraction has superconstant depth.

The fixed-minor-free extension sits here:

• fixed-minor-free-hardware-syndrome-depth-barrier.md
• weighted-excluded-minor-separator-theorem.md

For square-like 2D grids, the separator size is \(O(\sqrt N)\), giving the familiar \(\Omega(n/\sqrt N)\) law. With \(N=\Theta(n)\), this is \(\Omega(\sqrt n)\).

Conjecture Linkage

This lesson explains the safest theorem-backed part of Conjecture 3:

• static 2D local syndrome extraction is already hard for good QLDPC families;
• Quantum Tanner families supply theorem-level good-code examples;
• SWAP-only compilation is at least as constrained as general 2D-local syndrome extraction in this static model.

So the remaining frontier must be stated more carefully. It is not enough to repeat the static theorem. The live problem is to connect the lower bound to a robust CD(T_n,G) object and to the exact compiler semantics one wants.

What This Does And Does Not Prove

This proves:

• a static 2D lower bound for theorem-level good Quantum Tanner families;
• a separator-based route for broader low-separator hardware in the stabilizer-measurement setting.

This does not prove:

• a full classical packet-routing interpretation of stabilizer demand;
• a general CD(T_n,G) theorem for every compiler model;
• that every generator presentation of every QLDPC family has the same expansion properties;
• that extra resources such as teleportation, bilayer locality, or hierarchical memories are excluded unless the model explicitly excludes them.

Active Recall

1. Derive \(\Omega(\sqrt n)\) from \(\Omega(k\sqrt d/m)\) for a good code with \(m=\Theta(n)\).
2. Why is this route presentation-invariant?
3. What does the separator meta-theorem add beyond square grids?
4. Which model assumptions are still essential?
5. Why does this not settle the whole CD(T_n,G) conjecture?

Next-Step Handoff

Next lesson: learn the explicit Quantum Tanner stack. The goal is to understand why the chosen-presentation route remains important even though the static theorem can be proved from parameters alone.