<p>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 <span class="math-container">$k$</span>-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").</p>

CC BY-SA 4.0
2020-04-03T22:59:01.597Z
thank you smapers!
raycosine
CC BY-SA 4.0
2020-04-03T08:41:02.583Z
2020-04-03T08:41:02.583Z
smapers
<p>I have been going through Kempe-Kitaev-Regev's paper <a href="https://arxiv.org/abs/quant-ph/0406180" rel="nofollow noreferrer"><em>The Complexity of the Local Hamiltonian Problem</em></a>. In the first paragraph of page 3, the authors point out that:</p>

<blockquote>
  <p>To the best of our knowledge, this is the ﬁrst reduction inside QMA (i.e., not from the circuit problem).</p>
</blockquote>

<p>What does 'not from the circuit problem' mean and what does the circuit problem refer to?</p>

<cc.complexity-theory><soft-question><quantum-computing>
What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper
raycosine
# What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

(Asked by: username_0 on 2020-04-03)

I have been going through Kempe-Kitaev-Regev's paper [*The Complexity of the Local Hamiltonian Problem*](https://arxiv.org/abs/quant-ph/0406180). 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?

**Tags:** cc.complexity-theory, soft-question, quantum-computing


---

## 1 answers

### Answer by username_1 on 2020-04-03. Score: 5 | Accepted 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").

> **Comments:**
> **username_0**: thank you username_1!  

---

