<p>The inclusion <span class="math-container">$EXP\subseteq QMA(2)$</span> is not known, and in fact is not expected to hold. It would imply that any exponential-size computation could be verified in polynomial time. In fact, the inclusion <span class="math-container">$QMA(2)\subseteq EXP$</span> is also unknown, according to Aaronson et al. [1].</p>
<p>The best known inclusions are</p>
<p><span class="math-container">$$QMA\subseteq QMA(2)\subseteq NEXP $$</span></p>
<p>[1] S. Aaronson, S. Beigi, A. Drucker, B. Fefferman and P. Shor. The power of unentanglement. Theory of Computing, 5(1):1-42, 2009. arXiv:0804.0802</p>

CC BY-SA 4.0
2024-06-19T21:10:53.210Z
2024-06-19T21:10:53.210Z
Lieuwe Vinkhuijzen
<p>I searched for references. But I could not find any. Is <span class="math-container">$EXP\subseteq QMA(2)$</span> known?</p>

<cc.complexity-theory><complexity-classes><quantum-computing>
On the power of QMA(2)
user72910
# On the power of QMA(2)

(Asked by: username_0 on 2024-06-19)

I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing


---

## 1 answers

### Answer by username_1 on 2024-06-19. Score: 2

The inclusion $EXP\subseteq QMA(2)$ is not known, and in fact is not expected to hold. It would imply that any exponential-size computation could be verified in polynomial time. In fact, the inclusion $QMA(2)\subseteq EXP$ is also unknown, according to Aaronson et al. [1].

The best known inclusions are

$$QMA\subseteq QMA(2)\subseteq NEXP $$

[1] S. Aaronson, S. Beigi, A. Drucker, B. Fefferman and P. Shor. The power of unentanglement. Theory of Computing, 5(1):1-42, 2009. arXiv:0804.0802


---

