Skip to content

Lesson 03 - Explicit Quantum Tanner Family Stack

Goal

Understand the explicit-family mechanism behind the Quantum Tanner route: diagonal expansion, incidence expansion, local-generator blow-up, and parity-Tanner expansion.

Prerequisites And Diagnostic Checks

  1. What is a Tanner graph for a parity-check matrix?
  2. What is a local code in a Tanner-code construction?
  3. What does a spectral gap imply for expansion in a regular graph?
  4. Why might a local blow-up preserve expansion only under an additional gadget condition?

Concrete Motivation

The static theorem can use only \(k,d=\Theta(n)\), but the conjectured compiler-native barrier needs more structure. It wants to know where the syndrome demands live.

Quantum Tanner codes give that structure. The construction places qubits and local checks on a left-right Cayley complex. The local graph records a chain:

  1. diagonal graphs expand;
  2. expansion transfers to square-vertex incidence;
  3. local generators form a constant-size blow-up of that incidence structure;
  4. under a local gadget condition, the chosen parity-Tanner presentation is a local expander.

Worked Example Before Abstraction

Imagine a regular expander graph \(G\). Replace each vertex by a constant-size gadget and connect gadgets according to the original edges. If the gadget has a positive boundary property, a set that is small and nontrivial inside many gadgets must expose boundary in many places.

This is the intuition behind the Quantum Tanner local-generator blow-up:

  • global expansion comes from the diagonal or incidence graph;
  • local tensor-code structure supplies the constant-size check gadget;
  • a connected basis and no-zero-coordinate condition prevent local checks from hiding entirely inside one side of a cut.

The hard part is not that one gadget expands. The hard part is making the local-to-global transfer deterministic and compatible with the exact stabilizer presentation.

Formal Stack

The current explicit-family attack stack is:

  1. quantum-tanner-diagonal-expansion-structure.md
  2. quantum-tanner-incidence-spectral-gap.md
  3. spectral-gap-to-regular-graph-expansion.md
  4. regular-graph-expansion-to-incidence-expansion.md
  5. quantum-tanner-local-generator-blowup.md
  6. incidence-expansion-to-parity-tanner-expansion.md
  7. connected-basis-for-nonzero-coordinate-code.md
  8. dual-distance-excludes-zero-coordinates.md
  9. tensor-product-preserves-no-zero-coordinates.md
  10. quantum-tanner-theorem17-parity-expander.md

The route can be read as:

spectral expansion -> incidence expansion -> local-generator blow-up -> parity-Tanner expansion -> static 2D chosen-presentation barrier.

Theorem Versus Bridge

The graph currently treats this as a theorem-backed chosen-presentation route when the local hypotheses are satisfied. It is not the same as a presentation-invariant statement.

That distinction matters.

If we prove that one chosen generator matrix has a strongly expanding Tanner graph, then we get a syndrome-depth lower bound for measuring that presentation. But a stabilizer code is a subspace, and a different generating set can change the Tanner graph.

That is why Lessons 04 and 05 replace raw generator crossings by stabilizer cut rank.

Conjecture Linkage

This explicit-family stack matters because Conjecture 3 is not only a black-box code-parameter statement. The conjectured CD(T_n,G) route wants a demand object. Quantum Tanner structure is where one tries to identify that object concretely.

For the current graph:

  • the static 2D theorem can be closed without this stack;
  • the chosen-presentation CD intuition uses this stack heavily;
  • the intrinsic balanced-cut-rank frontier tries to upgrade this stack into a generator-invariant statement.

What This Does And Does Not Prove

This proves or supports:

  • a deterministic conditional path from Quantum Tanner construction data to parity-Tanner local expansion;
  • a chosen-presentation barrier close to the intuitive expander-versus-grid mechanism.

This does not prove:

  • that every stabilizer generating set has the same expansion;
  • that local expansion alone implies intrinsic cut rank;
  • that tester-side expansion automatically becomes original-qubit matroid connectivity.

Active Recall

  1. Why is local-generator blow-up not automatically expansion-preserving?
  2. What role does the no-zero-coordinate condition play?
  3. Why keep a chosen-presentation theorem if a presentation-invariant static theorem already exists?
  4. Where does the stack still fail to prove CD(T_n,G)?
  5. What would a deterministic component-code package add?

Next-Step Handoff

Next lesson: replace generator crossings by the invariant object, stabilizer cut rank, and learn why it is a binary matroid connectivity function.