Speaker Affiliation: University of California Santa Barbara
Title: Tunneling in Quantum Adiabatic Optimization
Abstract: This talk will address several aspects of tunneling when attempting quantum adiabatic optimization (QAO). First, I derive how the width and height of potential barriers affect the minimal spectral gap of the QAO algorithm. This derivation uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone. Next, I discuss to which extend the asymptotic scaling of spectral gaps is relevant for reasonably sized systems. For tunneling we will see that the asymptotic behavior of the spectral gap does not accurately describe the exact gap behavior for systems of less than 10^12 qubits. Lastly, we ask what happens if we run the QAO algorithm faster than the adiabatic condition prescribes, i.e. if we perform non-adiabatic (or diabetic) optimization. I will show that typically the runtime suggested by the adiabatic theorem is not only a sufficient, but also necessary. This result indicates that for generic problem instances non-adiabatic optimization will not outperform QAO, although there are atypical exceptions to this rule.