Quantum Optimization with Rydberg Atom Arrays beyond Unit Disk Graphs

Programmable quantum systems based on Rydberg atom arrays are a promising platform for tests of quantum optimization algorithms with hundreds of qubits. In particular, the maximum independent set problem on so-called unit-disk graphs has a natural realization in such systems. In this talk I discuss strategies to extend the classes of problems that can be effciently encoded in Rydberg arrays by constructing explicit mappings from several generic optimization problems to maximum weighted independent set problems on unit-disk graphs, with at most a quadratic overhead in the number of qubits. This includes: maximum weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary connectivity, and integer factorization formulated as an optimization problem. This provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity.