# Local Hamiltonian and combinatorial search problems

I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination search problem. I am not getting the intuition behind this. Let me quote from the second paragraph of the chapter.

There is hope that there may be combinatorial search problems, defined on $n$ bits so that $N = 2^n$ , where for certain “interesting” subsets of the instances the run time of the Quantum Adiabatic Algorithm grows sub-exponentially in $n$. A positive result of this kind would greatly expand the known power of quantum computers.

I understand that it is possible to implement the Grover's algorithm as an adiabatic quantum algorithm. What I don't understand is the special relation between local Hamiltonian and combinatorial search problems. Any clue?

• Just to clarify, I would like to know an example of local structure in a combinatorial search problem. – Omar Shehab Oct 17 '13 at 23:53