RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Tunneling in Quantum Adiabatic Optimization

March 29, 2017 - 11:00am
Wim van Dam
University of California, Santa Barbara

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. 
This is joint work with Lucas Brady. 
CSS 3100A