Rydberg-blockade-based parity quantum optimization*

A major research effort in quantum information science focuses on exploring a potential quantum advantage in the solution of combinatorial optimization problems on near-term quantum devices. A particularly promising platform implementing quantum optimization algorithms are arrays of trapped neutral atoms, laser coupled to highly excited Rydberg states. However, encoding arbitrary combinatorial optimization problems in atomic arrays is challenging due to limited interqubit connectivity of the finite-range dipolar interactions. Here, we present a scalable architecture for solving higher-order constrained binary optimization problems on current neutral-atom hardware operating in the Rydberg blockade regime. A paradigmatic combinatorial optimization problem directly encodable on such devices is the maximum-weight independent set (MWIS) problem on disk graphs. We extend this approach to generic combinatorial optimization problems by utilizing the recently developed parity encoding of arbitrary connected higher-order constrained optimization problems. The parity encoding only requires problem-encoding local fields and problem-indepedent quasi-local interactions among 2 x 2 plaquettes of nearest-neighbor physical qubits on a square lattice geometry. We formulate the required plaquette-logic as MWIS problem, which allows one to build our architecture from small MWIS modules in a problem-independent way, crucial for practical scalability. Furthermore, we provide an efficient method to compensate for the long-range interaction tails of the van der Waals interaction between Rydberg atoms.