Oral: Quantum Routing and Entanglement Capacity Through Bottlenecks

To implement arbitrary quantum interactions in architectures with restricted geometries, one may effectively simulate all-to-all connectivity by routing quantum information. In order to implement general quantum operations and constrain the cost of doing so, we would like to find optimal protocols and lower bounds for routing. We consider the entanglement dynamics and routing between two regions only connected through an intermediate region with few vertices that forms a bottleneck. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph G, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the entangling rate and therefore on the routing time. 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 δ we show a lower bound of Ω(N_L^(1/2-δ)/N_C) on the routing time, which also implies a similar lower bound on the average entangling rate. We also prove an upper bound on the average entangling capacity of a local Hamiltonian with a bottleneck. As a special case, when applied to the star graph (i.e., one vertex connected to N leaves), we obtain an Ω(N^(1/2-δ)) lower bound on the routing time and on the time to prepare Ω(N) Bell pairs between the vertices. We also show that in systems of free fermions, we can route optimally on the star graph in time Θ(√N), illustrating a separation between gate-based and Hamiltonian quantum routing.