  We consider the adiabatic quantum algorithm for systems with "no sign
problem", such as the transverse field Ising mode, and analyze the
equilibration time for quantum Monte Carlo (QMC) on these systems. We ask: if
the spectral gap is only inverse polynomially small, will equilibration methods
based on slowly changing the Hamiltonian parameters in the QMC simulation
succeed in a polynomial time? We show that this is not true, by constructing
counter-examples. Some examples are Hamiltonians where the space of
configurations where the wavefunction has non-negligible amplitude has a
nontrivial fundamental group, causing the space of trajectories in imaginary
time to break into disconnected components, with only negligible probability
outside these components. For the simplest example we give with an abelian
fundamental group, QMC does not equilibrate but still solves the optimization
problem. More severe effects leading to failure to solve the optimization can
occur when the fundamental group is a free group on two generators. Other
examples where QMC fails have a trivial fundamental group, but still use ideas
from topology relating group presentations to simplicial complexes. We define
gadgets to realize these Hamiltonians as the effective low-energy dynamics of a
transverse field Ising model. We present some analytic results on equilibration
times which may be of some independent interest in the theory of equilibration
of Markov chains. Conversely, we show that a small spectral gap implies slow
equilibration at low temperature for some initial conditions and for a natural
choice of local QMC updates.
