Abstract
Quantum adiabatic optimization (QAO) was one of the first quantum algorithms to be proposed for combinatorial optimization, but in spite of its long history the search for a quantum speedup with QAO still remains elusive. This inability to find a speedup is often attributed to the use of stoquastic Hamiltonians, because ground states of these models can in many cases be efficiently classically simulated by Markov chain Monte Carlo methods. In this talk I'll start by reviewing aspects of the general stoquastic simulation conjecture, with a particular focus on the role of the adiabatic path in these simulations. More recently, this threat of classical simulation has motivated proposals to consider the use of general (nonstoquastic) Hamiltonians in QAO. To further our understanding of these proposals I'll present a general isoperimetric inequality that constrains the spectral gap of a Hamiltonian in terms of its quantum ground state geometry, without a dependence on the details of the interaction couplings. This result can be applied to see that some explicit probability distributions, even ones which are simple to describe, will inevitably take exponential time to be precisely reached by pure adiabatic evolution with local Hamiltonians.