# What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

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 ﬁrst 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

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").

• thank you smapers! Apr 3 '20 at 22:59