Skip to content

Token-Crossing Extraction Fails For SWAP-Only Compilation

Claim/Theorem

The token-crossing form of the SWAP-only execution-graph extraction lemma is false even in the smallest cross-cut stabilizer example.

Let a hardware cut L separate two adjacent physical sites u\in L and v\in L^c. Place data qubits q_u at u and q_v at v, together with an ancilla a also at u. Let the measured stabilizer space be

\[ \mathcal S=\operatorname{span}\{Z_{q_u}Z_{q_v}\}. \]

Then

\[ \chi_L(\mathcal S)=1, \]

because \(\mathcal S_L=\mathcal S_{L^c}=\{0\}\) and the unique nonzero stabilizer has support on both sides of the cut.

But there is a standard nearest-neighbor SWAP-free syndrome-extraction circuit for this stabilizer: prepare a in |0\rangle, apply \mathrm{CNOT}(q_u\to a), apply \mathrm{CNOT}(q_v\to a) across the cut edge (u,v), and then measure a. No qubit, ancilla, or logical token ever crosses \partial L. So any extracted multiset of token paths based only on actual token traversals of cut edges has total crossing count 0, not Omega(\chi_L(\mathcal S)).

Therefore the literal token-crossing version of [[swap-only-compiler-extraction-reduces-cd-to-stabilizer-cut-rank.md]] is false, even inside the static measurement-free SWAP-only regime. What the circuit does consume is one unit of cut-edge service: a cross-cut nearest-neighbor two-qubit gate. So the right compiler-native quantity must count cut-edge interaction service or cross-cut meetings, not only token crossings.

This fits the older matching route already on the graph: [[cross-cut-matching-service-bound.md]] lower-bounds depth from the amount of cross-cut interaction service demanded by a matching, not from literal token crossings.

Dependencies

  • [[cross-cut-stabilizer-rank.md]]
  • [[swap-only-compiler-extraction-reduces-cd-to-stabilizer-cut-rank.md]]
  • [[cross-cut-matching-service-bound.md]]

Conflicts/Gaps

  • This refutes only the token-crossing formulation. It does not refute a refined service-based or meeting-based extraction theorem.
  • The example has \chi_L=1 and no expander structure; it isolates the abstraction error, not the asymptotic Conjecture-3 lower bound.
  • A satisfactory replacement still needs to say how general SWAP-only compilers generate cut-edge service from intrinsic cut rank without appealing to a chosen Tanner presentation.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.1007/BF01215349