How does interaction geometry constrain STP?
Restrict pair measurements to an interaction graph. Characterize classical simulation, universal computation, and routing overhead on paths, trees, and lattices.
Discuss this questionFor a fixed family of interaction graphs, allow STP only on graph edges and characterize efficient simulation and universal computation with explicit routing costs. Keep prepared entanglement, fresh qubits, and adaptive control assumptions visible.
Why this is interesting
All-to-all access can hide a significant physical and algorithmic resource. Local models may expose an especially clear boundary.
Explicit variants
Depth overhead in one and two dimensions
For nearest-neighbor STP on a one-dimensional chain and a two-dimensional lattice, give universal constructions or obstructions and bound the depth overhead relative to an explicitly chosen all-to-all protocol. Count routing, fresh resources, and any preprocessing used to prepare long-range correlations.
A place to start
Compare paths, trees, and a two-dimensional lattice for the same small protocol, then seek a simulation bound parameterized by interaction-history width.
Related work
These works provide context and established results. They need not be the origin of this exact formulation.
Discuss this question
Reading is public. Posting requires a GitHub account. You can also write to Kunal.