Skip to content

Dense Tangle Breadth Forces Balanced Cut Rank

Claim/Theorem

Let \(M\) be a binary matroid on ground set \(E\) with \(|E|=n\), and fix a balance parameter \(0<\beta\le 1/2\). Suppose \(M\) has a tangle \(T\) of order \(k\) and breadth \(t\). If

\[ t>(1-\beta)n+k-2, \]

then every \(\beta\)-balanced cut \(L\subseteq E\), meaning

\[ \beta n \le |L| \le (1-\beta)n, \]

satisfies

\[ \lambda_M(L)\ge k-1. \]

Equivalently, if \(M\) is the column matroid of a full-row-rank stabilizer matrix for a stabilizer space \(\mathcal S\), then every \(\beta\)-balanced qubit cut satisfies

\[ \chi_L(\mathcal S)\ge k-1. \]

By [[cut-rank-is-interface-state-dimension.md]], every such cut carries at least k-1 binary interface-state bits in an optimal tree realization. By [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]], any measurement-free SWAP-only syndrome-extraction circuit on hardware \(G_{\mathrm{hw}}\) therefore obeys

\[ \operatorname{depth}(C) \;\ge\; \frac{k-1}{16\,|\partial_{G_{\mathrm{hw}}}L|} \]

for every hardware bottleneck cut \(L\) that is \(\beta\)-balanced on the qubits.

Proof sketch:

  1. [[tangle-breadth-gives-k-connected-set.md]] gives a \(t\)-element \(k\)-connected set \(Z\subseteq E\).
  2. Since \(t>(1-\beta)n+k-2\), the density hypothesis in [[dense-k-connected-set-forces-balanced-cut-rank.md]] applies to \(Z\).
  3. Hence every \(\beta\)-balanced cut has \(\lambda_M(L)\ge k-1\).
  4. [[cross-cut-stabilizer-rank-rank-formula.md]] identifies \(\lambda_M(L)\) with \(\chi_L(\mathcal S)\) in the stabilizer case.
  5. [[cut-rank-is-interface-state-dimension.md]] and [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]] convert the same lower bound into interface-state and compiler-depth language.

So the cleanest currently supported intrinsic closing theorem is now: dense tangle breadth is enough.

Dependencies

  • [[tangle-breadth-gives-k-connected-set.md]]
  • [[dense-k-connected-set-forces-balanced-cut-rank.md]]
  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[cut-rank-is-interface-state-dimension.md]]
  • [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]]

Conflicts/Gaps

  • This is a conditional intrinsic theorem, not yet a theorem about the actual Quantum Tanner or left-right-Cayley parity-check matroids.
  • The current graph supplies high tangle order, branchwidth, parity-Tanner expansion, and local testability style statements, but not a theorem proving breadth t>(1-\beta)n+k-O(1) in the original parity-check matroid.
  • Therefore the missing intrinsic hypothesis is now isolated more sharply than before: either prove dense tangle breadth directly, or prove some alternative structural statement that yields a dense \(k\)-connected set, such as a dense large-rank lean bag.

Sources

  • 10.37236/12467
  • 10.48550/arXiv.2109.14599
  • 10.48550/arXiv.0711.1383