3
$\begingroup$

Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)

$\endgroup$

1 Answer 1

4
$\begingroup$

This is not currently known. In my MSc. thesis, I show that, if it were true, then a consequence would be that $NP^{NP}\subseteq QMA$ (Theorem 21, below). I conjecture that in fact $coNP\subseteq QMA$ implies $PH\subseteq QMA$, but I was not able to prove that.

Lemma 14. $NP^{QMA\cap coQMA}\subseteq QMA$.

Theorem 21. If $QMA$ contains $co\text-NP$, then $NP^{NP}\subseteq QMA$

Proof. If $QMA$ contains $coNP$, then, equivalently, $NP\subseteq coQMA$, so we have $NP\subseteq QMA\cap coQMA$. Plugging this in, we get $NP^{NP}\subseteq NP^{QMA\cap coQMA}\subseteq QMA$. $\square$

The thesis contains other consequences, and variations and generalizations of this theorem.

$\endgroup$

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.