  Programmable quantum systems based on Rydberg atom arrays have recently been
used for hardware-efficient tests of quantum optimization algorithms [Ebadi et
al., Science, 376, 1209 (2022)] with hundreds of qubits. In particular, the
maximum independent set problem on so-called unit-disk graphs, was shown to be
efficiently encodable in such a quantum system. Here, we extend the classes of
problems that can be efficiently encoded in Rydberg arrays by constructing
explicit mappings from a wide class of problems to maximum weighted independent
set problems on unit-disk graphs, with at most a quadratic overhead in the
number of qubits. We analyze several examples, including: maximum weighted
independent set on graphs with arbitrary connectivity, quadratic unconstrained
binary optimization problems with arbitrary or restricted connectivity, and
integer factorization. Numerical simulations on small system sizes indicate
that the adiabatic time scale for solving the mapped problems is strongly
correlated with that of the original problems. Our work provides a blueprint
for using Rydberg atom arrays to solve a wide range of combinatorial
optimization problems with arbitrary connectivity, beyond the restrictions
imposed by the hardware geometry.
