Skip to content

Packet Routing O(C Plus D)

Claim/Theorem

Given any network together with edge-simple routes for a packet set, if the chosen routes have congestion \(c\) and dilation \(d\), then there exists a schedule completing the routing in \(O(c+d)\) steps. Therefore any local SWAP-only compilation that realizes interactions by moving quantum states along fixed local paths has depth at least \(\Omega(\max\{c,d\})\), and cut-induced congestion is a legitimate lower-bound witness.

Dependencies

  • None.

Conflicts/Gaps

  • The theorem is classical packet routing, not a quantum-circuit theorem.
  • Using it for coherent SWAP-only compilation assumes the usual abstraction that each SWAP layer behaves like a local routing step and that no extra nonlocal primitive, teleportation, or measurement-assisted shortcut is available.
  • This node supports the CD viewpoint of Conjecture 3, but it does not by itself identify the right source-sink pairs for a Tanner syndrome layer.

Sources

  • 10.1007/BF01215349