  We study the glued-trees problem of Childs et. al. in the adiabatic model of
quantum computing and provide an annealing schedule to solve an oracular
problem exponentially faster than classically possible. The Hamiltonians
involved in the quantum annealing do not suffer from the so-called sign
problem. Unlike the typical scenario, our schedule is efficient even though the
minimum energy gap of the Hamiltonians is exponentially small in the problem
size. We discuss generalizations based on initial-state randomization to avoid
some slowdowns in adiabatic quantum computing due to small gaps.
