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

up vote 5 down vote accepted

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.

  • 1
    Thanks for the answer. I had one more query, slightly unrelated to my main question. What does it essentially mean for a problem to be in $P^{QMA}$? How can we have a fully deterministic algorithm for a problem by querying probabilistic oracles which have a non-zero probability of giving out one or multiple incorrect answers in response to our queries? – BlueLagoon Oct 9 at 6:03
  • 1
    @BlueLagoon: Something you have to bear in mind is that these classes aren't necessarily defined in a way which corresponds to a "natural machine model". The mathematical definition of $\mathrm{P^{QMA}}$ are those problems solvable by a TM, in polynomial time, if we give it access to an oracle which could solve any problem in $\mathrm{QMA}$ in constant time. In this definition we aren't saying anything about how the oracle manages to do this, e.g. how it manages to decide NO instances given that $\mathrm{QMA}$ is in a sense a class only about verifying YES instances. (1/2) – Niel de Beaudrap Oct 9 at 8:24
  • 1
    The main thing is that $\mathrm{QMA}$ is in principle a well-defined mathematical object (a set of languages), and we can consider another ('hypothetical') mathematical object, a $\mathrm{QMA}$ oracle, which decides some $L \in \mathrm{QMA}$ in constant time. We can then use this in a spiced-up model of computation involving a TM with access to such an oracle. The oracle doesn't have to reflect that the usual definition of $\mathrm{QMA}$ involves a probabilistic procedure: by construction it always produces the correct answer. If this strikes you as unrealistic, that's because it is. :-) (2/2) – Niel de Beaudrap Oct 9 at 8:28

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.