Minimizing AOD Trap Activations for Atom Shuttling in Neutral-Atom Quantum Architectures

Neutral-atom quantum computers store quantum information in atoms confined by optical traps. Unlike superconducting architectures, neutral-atom platforms can shuttle atoms across the processor using acousto-optic deflector (AOD) movable traps to shuttle atoms before gate execution. When compiling quantum circuits for neutral-atom devices, minimizing the number of AOD traps activations is crucial, since each activation increases the physical overhead of the computation. We introduce a matrix-based optimization problem that models the AOD traps activation scheme and prove that finding an optimal solution is an NP-hard problem. As a consequence, determining the minimum number of AOD activations required to shuttle a given set of atoms is also NP-hard. To solve practical instances of the problem, we encode it as an Answer Set Programming problem and evaluate the proposed approach experimentally on a set of benchmark instances. We further establish a correspondence between our formulation and Boolean Matrix Factorization (BMF), which opens the way to reusing existing BMF techniques for computing AOD activation schemes.