Alladi Ramakrishnan Hall

Quantum algorithms for combinatorial optimization with neutral atom arrays

Rhine Samajdar

Princeton University

Realizing quantum speedups for practically relevant, computationally hard problems is a central challenge in quantum information science. Using neutral atom arrays in two spatial dimensions, we investigate quantum algorithms for solving the Maximum Independent Set problem using a hardware-efficient encoding associated with Rydberg blockade. Exploring a class of graphs with programmable connectivity, we show a superlinear quantum speedup in finding exact solutions in the deep circuit regime and generalize our findings to demonstrate a quantum adiabatic speedup on a whole class of combinatorial optimization problems. In particular, we demonstrate that instances can either have a quantum speedup, including a naturally occurring Grover-type speedup, or a quantum slowdown depending on the degree of localization of the eigenstates involved in the level crossing, and we interpret the experimental observations in this context. We also study a family of problems with a superexponentially large time to solution via adiabatic evolution and illustrate the utility of quantum quenches as an algorithmic tool to remedy this problem.