Quantum Enhancement via Many-Body Localization

In 2009, Altshuler, Krovi, Roland raised an objection to the adiabatic quantum annealing program, noting that a phenomenon of Many-Body Localization occurs at the end of the protocol, resulting in exponentially small gaps. I revisit their estimates, and discuss how although these gaps generally render the closed-system protocol impractical, an enhancement over classical algorithms is possible for computational tasks that do not require reaching the end of adiabatic path.