Skip to content

2D Grid Bisection Width

Claim/Theorem

For the 2D array graph \(A^2 = P_a \times P_b\) with \(a \le b\), the bisection width is exactly \(a\). In particular, for a near-square static 2D grid with \(N = ab\) physical sites, the maximum number of edge-disjoint interactions that can cross a balanced vertical or horizontal cut in a single time step is \(\Theta(\sqrt{N})\).

Dependencies

  • None.

Conflicts/Gaps

  • This is a host-graph capacity statement. To turn it into a syndrome-extraction lower bound, one still needs a guest-demand statement saying that \(\Omega(n)\) logical interactions must traverse some balanced hardware cut during the round.
  • The asymptotic form becomes \(\Theta(\sqrt{N})\) only when the hardware footprint is roughly square; extremely skewed static grids need the exact formula \(bw(P_a \times P_b)=a\) instead.

Sources

  • 10.1016/S0166-218X(03)00265-8