Relation between $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$

Question

What is the relation between $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$ and how do we prove it? Are these classes equal?

Answer 1

Clearly $\mathrm{QMA \subseteq P^{QMA}}$, as we can construct a $\mathrm{P^{QMA}}$ algorithm to solve any problem in $\mathrm{QMA}$, by using an oracle call. The question is whether the reverse containment is known to hold. And the answer is that the reverse containment is not known to hold (and I think is not expected to hold).

Of course, computational complexity is full of classes where we don't know whether or not they're different — and where proving that classes are different (even when they're "obviously" different, as with $\mathrm{P}$ vs. $\mathrm{NP}$ or $\mathrm{BPP}$ vs. $\mathrm{BQP}$) seems to be much more difficult than proving that they're equal (even when it isn't obvious at all that they're equal, as with $\mathrm{PSPACE}$ vs. $\mathrm{IP}$). So if two classes are different but not "enormously" different, you might be waiting a long time to hear about a definitive proof.

Still, we can elaborate a little bit on the obstacles to showing that $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$ are equal, if you think that maybe they are equal. One point is that one of them is known to be closed under complements, and the other isn't.

•  $\mathrm{P^{QMA}}$ is clearly closed under complements. The model of computation which is the basis for the definition of $\mathrm{P^{QMA}}$ is a deterministic Turing machine which has access to a $\mathrm{QMA}$ oracle. We can produce a similar oracle machine for the complementary problem by switching the final status ACCEPT / REJECT of the original machine. Therefore, if a language $L$ belongs to $\mathrm{P^{QMA}}$, then the complementary language $\overline{L}$ also belongs to $\mathrm{P^{QMA}}$. (The same goes for any promise problems, as opposed to languages.)

• At present, it is not known whether $\mathrm{QMA}$ is closed under complement. Part of the problem is the same difficulty suffered by $\mathrm{NP}$ and $\mathrm{MA}$: there's no obvious way to construct an (efficient bounded error) verifier for certificates of NO instances of problems in $\mathrm{QMA}$, given that all you know about them is that their YES instances do admit efficient bounded error verifiers. In fact, based on the intuition drawn from computability theory which might lead one to think that $\mathrm{NP \ne coNP}$ (and that therefore $\mathrm{P \ne NP}$), one might well guess that $\mathrm{QMA}$ is not closed under complements.

Obviously, if $\mathrm{QMA = P^{QMA}}$, it would follow that $\mathrm{QMA}$ is closed under complement: but if $\mathrm{QMA}$ were closed under complement, you might also hope to be able to show that by other (possibly easier) means as well. For now, the fact that we're confused about one but not the other is a sort of suggestive, if not entirely reliable, higher-order evidence that these classes might be different.