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?
