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?

  • $\begingroup$ Just to clarify, I would like to know an example of local structure in a combinatorial search problem. $\endgroup$ Oct 17, 2013 at 23:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.