Nonadaptive 2D Nearest-Neighbor Lower Bound¶
Claim/Theorem¶
Rosenbaum shows that in the \(k\)D nearest-neighbor architecture, nonadaptive circuits for controlled operations and fanout require depth \(\Theta(n^{1/k})\); in 2D this is \(\Theta(\sqrt{n})\). The same paper also shows that if one allows an adaptive classical controller, then these operations can be implemented in constant depth up to polynomial size and width overhead. For Conjecture 3, this sharply separates the SWAP-only, measurement-free regime from models with classical adaptivity.
Dependencies¶
- None.
Conflicts/Gaps¶
- The operation family is fanout/controlled-\(U\), not a general Tanner syndrome-extraction layer.
- The upper-bound side uses a stronger model than the static SWAP-only target of Conjecture 3; this is a warning about model sensitivity, not a counterexample to the desired lower bound.
- This node links Conjecture 3 to Conjecture 2: once measurement or classical control enters, the geometry barrier can change qualitatively.
Sources¶
10.4230/LIPIcs.TQC.2013.29410.48550/arXiv.1205.0036