Spectral graph theory applied to simulating stoquastic adiabatic optimization

Quantum adiabatic optimization (QAO) slowly varies an initial Hamiltonian with an easy-to-prepare ground-state to a final Hamiltonian whose ground-state encodes the solution to some optimization problem. Currently, little is known about the performance of QAO relative to classical optimization algorithms as we still lack strong analytic tools for analyzing its performance. In this talk, I will unify the problem of bounding the runtime of one such class of Hamiltonians -- so-called stoquastic Hamiltonians -- with questions about functions on graphs, heat diffusion, and classical sub-stochastic processes. I will introduce new tools for bounding the spectral gap of stoquastic Hamiltonians and, by exploiting heat diffusion, show that one of these techniques also provides an optimal and previously unknown gap bound for particular classes of graphs. Using this intuition and combining heat diffusion with classical sub-stochastic processes, I will offer a classical adiabatic algorithm that exhibits behavior typically considered "quantum", such as tunneling.