Breakdown of the quantum adiabatic algorithm and its remedies in Rydberg atom arrays

Classical optimization problems can be solved by adiabatically preparing the ground state of a quantum Hamiltonian that encodes the problem. The performance of this approach is determined by the smallest gap encountered during the evolution. In this work, we consider the maximum independent set problem, which can be naturally encoded in the Hamiltonian describing an array of neutral Rydberg atoms. We present a general construction of instances of the problem for which the minimum gap decays superexponentially with system size, implying a superexponentially large time to solution via adiabatic evolution. Local degeneracies can cause the system to initially evolve and localize into a configuration far from the solution in terms of Hamming distance. Such behavior can be independently induced by tails of the Rydberg interaction as well. We investigate remedies to this problem and observe that quenches in these models exhibit signatures of quantum many-body scars. By quenching from a suboptimal configuration, states with a large overlap with the ground state can be efficiently prepared, illustrating the utility of quantum quenches as an algorithmic tool.