Skip to content

Cross-Cut Gate Service Lower Bounds Stabilizer Cut Rank

Claim/Theorem

Derived proof skeleton from Delfosse, Beverland, and Tremblay:

let \(C\) be a measurement-free local-Clifford syndrome-extraction circuit on hardware graph \(G_{\mathrm{hw}}\), built only from single-qubit and two-qubit unitary Clifford gates, followed by final single-qubit measurements. This includes the static SWAP-only compilers relevant to Conjecture 3. Assume \(C\) measures a commuting Pauli generating family \(G\subseteq\mathcal S\) for stabilizer space \(\mathcal S\).

For any hardware cut \(L\), define the cut-edge service of \(C\) across \(L\) by

\[ \operatorname{serv}_L(C) \;:=\; \#\{\text{two-qubit gates of }C\text{ supported on both }L\text{ and }L^c\}. \]

Then the doubled-circuit mutual-information proof of 10.48550/arXiv.2109.14599 sharpens from a depth bound to the service bound

\[ \operatorname{serv}_L(C)\;\ge\;\frac{1}{16}\,n_{\mathrm{cut}}(G,L) \;\ge\; \frac{1}{16}\,\chi_L(\mathcal S). \]

Proof skeleton:

  1. In the measurement-free setting there are no intermediate measurements or classically-controlled corrections to postpone, so the doubled circuit uses the same unitary block twice, separated by the random Pauli error layer from Section 4 of Delfosse-Beverland-Tremblay.
  2. The lower bound from their Lemma 4 is unchanged:
\[ I(O_{\bar L}^{(2)},E_{\bar L};O_{\bar R}^{(2)},E_{\bar R}\mid O^{(1)}) \;\ge\; \frac{1}{2}\,n_{\mathrm{cut}}(G,L). \]
  1. In their Lemma 5 proof, Proposition 4 charges at most 4 units of quantum mutual information increase for each two-qubit gate crossing the cut. Instead of the coarse layer bound 4\,\mathrm{depth}(U)\,|\partial L|, one may sum this charge over the actual cross-cut two-qubit gates. One run of \(C\) therefore contributes at most 4 serv_L(C), and the doubled circuit contributes at most 8 serv_L(C).
  2. Combining the lower and upper bounds gives
\[ \frac{1}{2}\,n_{\mathrm{cut}}(G,L) \;\le\; 8\,\operatorname{serv}_L(C), \]

hence \(\operatorname{serv}_L(C)\ge n_{\mathrm{cut}}(G,L)/16\). 5. Finally, [[cross-cut-stabilizer-rank.md]] gives \(n_{\mathrm{cut}}(G,L)\ge \chi_L(\mathcal S)\) for every generating family \(G\) of \(\mathcal S\).

So intrinsic cut rank does force a service-based cut functional for measurement-free SWAP-only compilers. The remaining CD gap is no longer service across a fixed hardware cut. It is the lack of a canonical guest-graph or path-based formulation of that service demand.

Dependencies

  • [[cross-cut-stabilizer-rank.md]]
  • [[stabilizer-measurement-cut-lower-bound.md]]
  • [[token-crossing-extraction-fails-for-swap-only-compilation.md]]
  • [[cross-cut-matching-service-bound.md]]

Conflicts/Gaps

  • This is a derived sharpening of the proof of Lemma 5 in 10.48550/arXiv.2109.14599, not a theorem stated verbatim in the paper.
  • The argument is stated only for measurement-free unitary syndrome-extraction circuits with final local measurements. If mid-circuit measurements, two-qubit measurements, or adaptive classical control are allowed, one must restore the extra circuit-normalization bookkeeping from the source paper.
  • The bound is still compiler-side: it lower-bounds actual cut-edge service of a specific circuit. It does not yet identify a canonical guest graph T_n or a path-based CD(T_n,\mathfrak G) object whose congestion equals that service.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.1007/BF01215349