  There is a large ongoing research effort towards obtaining a quantum
advantage in the solution of combinatorial optimization problems on near-term
quantum devices. A particularly promising platform for testing and developing
quantum optimization algorithms are arrays of trapped neutral atoms,
laser-coupled to highly excited Rydberg states. However, encoding combinatorial
optimization problems in atomic arrays is challenging due to the limited
inter-qubit connectivity given by their native finite-range interactions. Here
we propose and analyze a fast, high fidelity four-body Rydberg parity gate,
enabling a direct and straightforward implementation of the
Lechner-Hauke-Zoller (LHZ) scheme and its recent generalization, the parity
architecture, a scalable architecture for encoding arbitrarily connected
interaction graphs. Our gate relies on onetime-optimized adiabatic laser pulses
and is fully programmable by adjusting two hold-times during operation. We
numerically demonstrate an implementation of the quantum approximate
optimization algorithm (QAOA) for a small scale test problem. Our approach
allows for efficient execution of variational optimization steps with a
constant number of system manipulations, independent of the system size, thus
paving the way for experimental investigations of QAOA beyond the reach of
numerical simulations.
