it happens, physicists have almost a century of experience in analyzing these spectral gaps, but not for the purpose of deciding whether they decrease polynomially or exponentially as the number of particles increases to infinity!

Such hands-on analysis of the adiabatic algorithm was necessary, since van Dam et al. also showed that there is no black-box proof that the algorithm takes exponential time.  This is because, given a variable assignment $X$ to the 3SAT instance $\varphi$, the adiabatic algorithm computes not merely *whether* $X$ satisfies $\varphi$, but also how many clauses it satisfies.  And this information turns out to be sufficient to reconstruct $\varphi$ itself.

Recently Reichardt [@reichardt], building on work of Farhi, Goldstone, and Gutmann [@fgg], has constructed 3SAT instances for which the adiabatic algorithm takes polynomial time, whereas simulated annealing takes exponential time.  These instances involve a narrow obstacle along the path to the global optimum, which simulated annealing gets stuck at but which the adiabatic algorithm tunnels past.  On the other hand, these instances are easily solved by other classical algorithms.  An interesting open question is whether there exists a family of black-box functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\mathbb{Z}$ for which the adiabatic algorithm finds a global minimum using 