To implement arbitrary quantum interactions in architectures with restricted topologies, one may simulate all-to-all connectivity by routing quantum information. Therefore, it is of natural interest to find optimal protocols and lower bounds for routing. We consider a connectivity graph, G, of 2 regions connected only through an intermediate region of a small number of qubits that form a vertex bottleneck. Existing results only imply a trivial lower bound on the entangling rate and routing time across a vertex bottleneck. In our work, we significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with a tripartition of N_L, N_C, N_R qubits, for any arbitrarily small positive constant d we show a lower bound of Ω(max(N_L, N_R)^{1/2-d}/N_C) on the routing time. As a special case, when applied to the star graph, i.e., 1 node connected to N separated nodes, we improve an Ω(1) lower bound on the routing time to Ω(√N). We also give an optimal protocol for routing through bottlenecks in fermionic systems.
Pizza and drinks will be served after the seminar in ATL 2117.
