Expander Cut To Crossing Matching¶
Claim/Theorem¶
Let \(B=(V,E)\) be a bounded-degree bipartite graph with maximum degree \(\Delta\) and edge expansion bounded below by a constant \(h>0\) in the sense that every vertex subset \(S\subseteq V\) with \(|S|\le |V|/2\) has at least \(h|S|\) edges leaving it. If a hardware cut induces a balanced guest-vertex partition with \(\beta |V| \le |S| \le |V|/2\) for some constant \(\beta>0\), then the number of guest edges crossing the partition is at least \(h\beta |V|=\Omega(|V|)\). Moreover, because a bipartite multigraph admits a proper \(\Delta\)-edge-coloring, one color class contains at least \(\Omega(|V|/\Delta)=\Omega(|V|)\) crossing edges, and that color class is a matching. Therefore a single syndrome-extraction sublayer already contains a linear-size set of pairwise disjoint cross-cut interactions.
Dependencies¶
- [[quantum-tanner-expander-anchor.md]]
Conflicts/Gaps¶
- This lemma uses the expansion hypothesis abstractly; for a specific code family one must verify that the relevant syndrome-incidence graph is the expanding object being partitioned.
- Inside the stabilizer-measurement model, [[contracted-expansion-to-cross-cut-stabilizers.md]] is a more direct way to count cut stabilizers without passing through edge-coloring. The present node remains useful when one wants routed Tanner-edge or matching language closer to SWAP-only compilation.
- The conclusion is most natural in the standard coherent syndrome-extraction model with persistent check registers across all edge-color classes. If the compiler is allowed to materialize and discard more exotic ancilla gadgets, the guest graph to which the cut argument applies may need to be reformulated.
- The claim is a synthesis of expansion plus bipartite edge-coloring rather than a single theorem from one paper.
Sources¶
10.1109/FOCS54457.2022.0011710.1007/s004930170002