I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that:

To the best of our knowledge, this is the first reduction inside QMA (i.e., not from the circuit problem).

What does 'not from the circuit problem' mean and what does the circuit problem refer to?


1 Answer 1


QMA is defined as the set of problems for which there is a polynomial quantum "verifier" circuit. So I guess the "circuit problem" refers to deciding whether such a verifier circuit has an accepting input. QMA-completeness of the $k$-local Hamiltonian problem is typically proven by encoding this circuit in a Hamiltonian (i.e., "by reduction from the circuit problem"). In this paper instead they prove QMA-completeness of 2-local Hamiltonians by reduction from 3-local Hamiltonians (hence, "not from the circuit problem").

  • $\begingroup$ thank you smapers! $\endgroup$
    – raycosine
    Apr 3, 2020 at 22:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.