Cross-Cut Matching Service Bound¶
Claim/Theorem¶
Let \(H\) be a static near-square 2D grid with \(N\) physical sites, and let \(C\) be a balanced geometric cut of \(H\). Since the cut contains only \(\Theta(\sqrt{N})\) hardware edges, any SWAP-only nearest-neighbor schedule can realize at most \(O(\sqrt{N})\) cross-cut two-qubit interactions in one time step. Consequently, if a compilation must realize a matching of \(M\) logical interactions whose endpoints begin on opposite sides of the cut, then the schedule depth is at least
\[
\Omega(M / \sqrt{N}).
\]
Each such logical interaction must consume some cut edge-time at least once, because the two participating registers can only meet by using a nearest-neighbor interaction across the cut.
Dependencies¶
- [[2d-grid-bisection-width.md]]
- [[packet-routing-o-c-plus-d.md]]
Conflicts/Gaps¶
- This is a cut-capacity lower bound for SWAP-only local compilation; it does not apply once teleportation, long-range couplers, or measurement-assisted nonlocal primitives are allowed.
- The statement assumes one logical register occupies one physical location at a time and that logical interactions are enacted by local two-qubit gates after routing.
- The bound is lower-order if the relevant hardware footprint is very skewed; the near-square assumption is what turns the cut size into \(\Theta(\sqrt{N})\).
Sources¶
10.1016/S0166-218X(03)00265-810.1007/BF01215349