Item

Abstract

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. Here, we consider the maximum independent set problem, which can be
efficiently encoded in the Hamiltonian describing a Rydberg atom array. 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. The small
gap arises from locally independent choices, which cause the system to
initially evolve and localize into a configuration far from the solution in
terms of Hamming distance. We investigate remedies to this problem.
Specifically, we show that quantum quenches in these models can exhibit
signatures of quantum many-body scars, which in turn, can circumvent the
superexponential gaps. By quenching from a suboptimal configuration, states
with a larger ground state overlap can be prepared, illustrating the utility of
quantum quenches as an algorithmic tool.