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.

Through a discussion of Cheeger inequalities, I will describe how the geometry of the ground-state is in one-to-one correspondence with the spectral gap of the corresponding Hamiltonian, and hence the runtime of both QAO and certain classical monte carlo techniques. Then, 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 a large class of graphs. Additionally, these methods suggest a novel, typically efficient classical simulation algorithm for QAO, sub-stochastic monte carlo.