as a quantum analogue of simulated annealing.  Their algorithm is easiest to describe in a continuous-time setting, using the concepts of a Hamiltonian (an operation that acts on a quantum state over an infinitesimal time interval $\Delta t$) and a ground state (the lowest-energy state left invariant by a given Hamiltonian).  The algorithm starts by applying a Hamiltonian $H_{0}$ that has a known, easily prepared ground state, then slowly transitions to another Hamiltonian $H_{1}$ whose ground state encodes the solution to (say) an instance of 3SAT.  The *quantum adiabatic theorem* says that if a quantum computer starts in the ground state of $H_{0}$, then it must end in the ground state of $H_{1}$, *provided the transition from* $H_{0}$* to* $H_{1}$* is slow enough*.  The key question is how slow is slow enough.

In their original paper, Farhi et al. [@fggllp] gave numerical evidence that the adiabatic algorithm solves random, critically-constrained instances of the $\mathsf{NP}$-complete Exact Cover problem in polynomial time.  But having learned from experience, most computer scientists are wary of taking such numerical evidence too seriously as a guide to asymptotic behavior.  This is especially true when the instance sizes are small ($n\leq20$ in Farhi et al.’s case), as 