Ising formulations of NP problems
So I've been reading Andy Lucas's paper Ising formulations of many NP problems -- which by the way is an excellent (gentle) introduction to Quantum Adiabatic Algorithm (QAA) optimization and NP problems. Here are some of my thoughts: Andy starts out with a review of the adiabatic theorem which can be simply expressed as:
$$ H(t) = \left(1 - \frac{t}{T} \right) H_0 + \frac{t}{T} H_p $$
Let's breakdown the theorem into smaller chunks. $H$ is the Hamiltonian (or state or configuration or energy configuration) of a system. So $H_p$ is a quantum Hamiltonian and it has a ground state (some ground state) that somehow corresponds to a known ground another state $H_0$ -- the key insight here is that $H_0$ is "easy" to determine (or experimentally configured). The theorem adiabatic theorem states that given enough time $T$ we'd have the solution. This is because if $t$ is small, ie $t \rightarrow 0$, then $H(t) = H_0$ and if $t \rightarrow T$ then $H(t) = H_p$.
Now that we've gotten the basic theorem out of the way, let's take a look at the paper's goal. Essentially, we wish to identify a problem of interest whose Hamiltonian $H_p$ can encode the ground state. Notice that $H_p$ has infinite states and perhaps one (or more) of those states has the lowest ground state energy configuration.