they have to be when simulating a quantum computer on a classical one.  On the other hand, Farhi relishes pointing out that if the empirically-measured running time were exponential, no computer scientist would dream of saying that it would eventually become polynomial!  In my opinion, the crucial experiment (which has not yet been done) would be to compare the adiabatic algorithm head-on against simulated annealing and other classical heuristics.  The evidence for the adiabatic algorithm’s performance would be much more convincing if the known classical algorithms took exponential time on the same random instances.

On the theoretical side, van Dam, Mosca, and Vazirani [@dmv] constructed 3SAT instances for which the adiabatic algorithm provably takes exponential time, at least when the transition between the initial and final Hamiltonians is linear.  Their instances involve a huge basin of attraction that leads to a false optimum (meaning most but not all clauses are satisfied), together with an exponentially small basin that leads to the true optimum.  To lower-bound the algorithm’s running time on these instances, van Dam et al. showed that the spectral gap (that is, the gap between the smallest and second-smallest eigenvalues) of some intermediate Hamiltonian decreases exponentially in $n$.  As 