  We describe and analyze an architecture for quantum optimization to solve
maximum independent set (MIS) problems using neutral atom arrays trapped in
optical tweezers. Optimizing independent sets is one of the paradigmatic,
NP-hard problems in computer science. Our approach is based on coherent
manipulation of atom arrays via the excitation into Rydberg atomic states.
Specifically, we show that solutions of MIS problems can be efficiently encoded
in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg
blockade mechanism. By studying the performance of leading classical
algorithms, we identify parameter regimes, where computationally hard instances
can be tested using near-term experimental systems. Practical implementations
of both quantum annealing and variational quantum optimization algorithms
beyond the adiabatic principle are discussed.
