Optimal Routing Protocols for Reconfigurable Atom Arrays

Neutral atom arrays have emerged as a promising platform for both analog and digital quantum processing. Recently, devices capable of reconfiguring arrays during quantum processes have enabled new applications for these systems. Atom reconfiguration, or routing, is the core mechanism for programming circuits; optimizing this routing can increase processing speeds, reduce decoherence, and enable efficient implementations of highly non-local connections. In this work, we investigate routing models applicable to state-of-the-art neutral atom systems. With routing steps that can operate on multiple atoms in parallel, we prove that current designs require Ω\(sqrt N log N\) steps to perform certain permutations on 2D arrays with N atoms and provide a protocol that achieves routing in mathcal O\(sqrt N log N\) steps for any permutation. We also propose a simple experimental upgrade and show that it would reduce the routing cost to Θ\(log N\) steps.