Quantum optimization on arbitrary graphs using Rydberg atom arrays

Programmable quantum simulators based on Rydberg atom arrays have been used to probe new quantum phases of matter, to explore new phenomena of non-equilibrium dynamics, and, more recently, to test quantum optimization algorithms. In an earlier proposal [Pichler et al., arXiv:1808.10816], the authors showed that Rydberg atom arrays can be used to encode the maximum independent set (MIS) problem on a particular ensemble of geometric graphs, the so-called unit disk graphs, without any encoding overhead. Here, by using ancillary qubits, we construct an explicit mapping from MIS on arbitrary graphs to MIS on unit-disk graphs, with at most a quadratic overhead. In addition, we extend the mapping to other hard combinatorial optimization problems such as MaxCut and 3-SAT. This provides a blueprint for using Rydberg atom arrays to solve many combinatorial optimization problems on arbitrary graphs, beyond the restrictions imposed by the hardware geometry.