Mixing
Relation between QMA and P^QMA
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
What is the relation between $mathrmQMA$ and $mathrmP^QMA$ and how do we prove it? Are these classes equal?
complexity-theory qma
edited 4 hours ago
Niel de Beaudrap
4,683830
asked 4 hours ago
BlueLagoon
61
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
What is the relation between $mathrmQMA$ and $mathrmP^QMA$ and how do we prove it? Are these classes equal?
complexity-theory qma
edited 4 hours ago
Niel de Beaudrap
4,683830
asked 4 hours ago
BlueLagoon
61
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
What is the relation between $mathrmQMA$ and $mathrmP^QMA$ and how do we prove it? Are these classes equal?
complexity-theory qma
edited 4 hours ago
Niel de Beaudrap
4,683830
asked 4 hours ago
BlueLagoon
61
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
What is the relation between $mathrmQMA$ and $mathrmP^QMA$ and how do we prove it? Are these classes equal?
complexity-theory qma
complexity-theory qma
edited 4 hours ago
Niel de Beaudrap
4,683830
asked 4 hours ago
BlueLagoon
61
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
Niel de Beaudrap
4,683830
asked 4 hours ago
BlueLagoon
61
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
Niel de Beaudrap
4,683830
edited 4 hours ago
Niel de Beaudrap
4,683830
edited 4 hours ago
Niel de Beaudrap
4,683830
4,683830
asked 4 hours ago
BlueLagoon
61
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
BlueLagoon
61
asked 4 hours ago
BlueLagoon
61
61
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
BlueLagoon is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Clearly $mathrmQMA subseteq P^QMA$, as a $mathrmP^QMA$ problem can solve any problem in $mathrmQMA$ with an oracle call. The question is then 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 $mathrmP$ vs. $mathrmNP$ or $mathrmBPP$ vs. $mathrmBQP$) seems to be much more difficult than proving that they're equal (as with $mathrmNL$ vs. $mathrmNL^NL$, or even $mathrmPSPACE$ vs. $mathrmIP$). 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 $mathrmQMA$ and $mathrmP^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.
 $mathrmP^QMA$ is clearly closed under complements.
The model of computation which is the basis for the definition of $mathrmP^QMA$ is a deterministic Turing machine which has access to a $mathrmQMA$ 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 $mathrmP^QMA$, then the complementary language $overlineL$ also belongs to $mathrmP^QMA$. (The same goes for any promise problems, as opposed to languages.)At present, it is not known whether $mathrmQMA$ is closed under complement. Part of the problem is the same difficulty suffered by $mathrmNP$ and $mathrmMA$: there's no obvious way to construct an (efficient bounded error) verifier for certificates of NO instances of problems in $mathrmQMA$, 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 $mathrmNP ne coNP$ (and that therefore $mathrmP ne NP$), one might well guess that $mathrmQMA$ is not closed under complements.
Obviously, if $mathrmQMA = P^QMA$, it would follow that $mathrmQMA$ is closed under complement: but if $mathrmQMA$ 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 fuzzy (i.e. suggestive, if not entirely reliable) higher-order evidence that these classes might be different.
answered 3 hours ago
Niel de Beaudrap
4,683830
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Clearly $mathrmQMA subseteq P^QMA$, as a $mathrmP^QMA$ problem can solve any problem in $mathrmQMA$ with an oracle call. The question is then 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 $mathrmP$ vs. $mathrmNP$ or $mathrmBPP$ vs. $mathrmBQP$) seems to be much more difficult than proving that they're equal (as with $mathrmNL$ vs. $mathrmNL^NL$, or even $mathrmPSPACE$ vs. $mathrmIP$). 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 $mathrmQMA$ and $mathrmP^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.
 $mathrmP^QMA$ is clearly closed under complements.
The model of computation which is the basis for the definition of $mathrmP^QMA$ is a deterministic Turing machine which has access to a $mathrmQMA$ 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 $mathrmP^QMA$, then the complementary language $overlineL$ also belongs to $mathrmP^QMA$. (The same goes for any promise problems, as opposed to languages.)At present, it is not known whether $mathrmQMA$ is closed under complement. Part of the problem is the same difficulty suffered by $mathrmNP$ and $mathrmMA$: there's no obvious way to construct an (efficient bounded error) verifier for certificates of NO instances of problems in $mathrmQMA$, 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 $mathrmNP ne coNP$ (and that therefore $mathrmP ne NP$), one might well guess that $mathrmQMA$ is not closed under complements.
Obviously, if $mathrmQMA = P^QMA$, it would follow that $mathrmQMA$ is closed under complement: but if $mathrmQMA$ 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 fuzzy (i.e. suggestive, if not entirely reliable) higher-order evidence that these classes might be different.
answered 3 hours ago
Niel de Beaudrap
4,683830
add a comment |Â
up vote
2
down vote
Clearly $mathrmQMA subseteq P^QMA$, as a $mathrmP^QMA$ problem can solve any problem in $mathrmQMA$ with an oracle call. The question is then 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 $mathrmP$ vs. $mathrmNP$ or $mathrmBPP$ vs. $mathrmBQP$) seems to be much more difficult than proving that they're equal (as with $mathrmNL$ vs. $mathrmNL^NL$, or even $mathrmPSPACE$ vs. $mathrmIP$). 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 $mathrmQMA$ and $mathrmP^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.
 $mathrmP^QMA$ is clearly closed under complements.
The model of computation which is the basis for the definition of $mathrmP^QMA$ is a deterministic Turing machine which has access to a $mathrmQMA$ 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 $mathrmP^QMA$, then the complementary language $overlineL$ also belongs to $mathrmP^QMA$. (The same goes for any promise problems, as opposed to languages.)At present, it is not known whether $mathrmQMA$ is closed under complement. Part of the problem is the same difficulty suffered by $mathrmNP$ and $mathrmMA$: there's no obvious way to construct an (efficient bounded error) verifier for certificates of NO instances of problems in $mathrmQMA$, 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 $mathrmNP ne coNP$ (and that therefore $mathrmP ne NP$), one might well guess that $mathrmQMA$ is not closed under complements.
Obviously, if $mathrmQMA = P^QMA$, it would follow that $mathrmQMA$ is closed under complement: but if $mathrmQMA$ 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 fuzzy (i.e. suggestive, if not entirely reliable) higher-order evidence that these classes might be different.
answered 3 hours ago
Niel de Beaudrap
4,683830
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Clearly $mathrmQMA subseteq P^QMA$, as a $mathrmP^QMA$ problem can solve any problem in $mathrmQMA$ with an oracle call. The question is then 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 $mathrmP$ vs. $mathrmNP$ or $mathrmBPP$ vs. $mathrmBQP$) seems to be much more difficult than proving that they're equal (as with $mathrmNL$ vs. $mathrmNL^NL$, or even $mathrmPSPACE$ vs. $mathrmIP$). 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 $mathrmQMA$ and $mathrmP^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.
 $mathrmP^QMA$ is clearly closed under complements.
The model of computation which is the basis for the definition of $mathrmP^QMA$ is a deterministic Turing machine which has access to a $mathrmQMA$ 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 $mathrmP^QMA$, then the complementary language $overlineL$ also belongs to $mathrmP^QMA$. (The same goes for any promise problems, as opposed to languages.)At present, it is not known whether $mathrmQMA$ is closed under complement. Part of the problem is the same difficulty suffered by $mathrmNP$ and $mathrmMA$: there's no obvious way to construct an (efficient bounded error) verifier for certificates of NO instances of problems in $mathrmQMA$, 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 $mathrmNP ne coNP$ (and that therefore $mathrmP ne NP$), one might well guess that $mathrmQMA$ is not closed under complements.
Obviously, if $mathrmQMA = P^QMA$, it would follow that $mathrmQMA$ is closed under complement: but if $mathrmQMA$ 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 fuzzy (i.e. suggestive, if not entirely reliable) higher-order evidence that these classes might be different.
answered 3 hours ago
Niel de Beaudrap
4,683830
Clearly $mathrmQMA subseteq P^QMA$, as a $mathrmP^QMA$ problem can solve any problem in $mathrmQMA$ with an oracle call. The question is then 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 $mathrmP$ vs. $mathrmNP$ or $mathrmBPP$ vs. $mathrmBQP$) seems to be much more difficult than proving that they're equal (as with $mathrmNL$ vs. $mathrmNL^NL$, or even $mathrmPSPACE$ vs. $mathrmIP$). 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 $mathrmQMA$ and $mathrmP^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.
 $mathrmP^QMA$ is clearly closed under complements.
The model of computation which is the basis for the definition of $mathrmP^QMA$ is a deterministic Turing machine which has access to a $mathrmQMA$ 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 $mathrmP^QMA$, then the complementary language $overlineL$ also belongs to $mathrmP^QMA$. (The same goes for any promise problems, as opposed to languages.)At present, it is not known whether $mathrmQMA$ is closed under complement. Part of the problem is the same difficulty suffered by $mathrmNP$ and $mathrmMA$: there's no obvious way to construct an (efficient bounded error) verifier for certificates of NO instances of problems in $mathrmQMA$, 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 $mathrmNP ne coNP$ (and that therefore $mathrmP ne NP$), one might well guess that $mathrmQMA$ is not closed under complements.
Obviously, if $mathrmQMA = P^QMA$, it would follow that $mathrmQMA$ is closed under complement: but if $mathrmQMA$ 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 fuzzy (i.e. suggestive, if not entirely reliable) higher-order evidence that these classes might be different.
answered 3 hours ago
Niel de Beaudrap
4,683830
edited 3 hours ago
answered 3 hours ago
Niel de Beaudrap
4,683830
answered 3 hours ago
Niel de Beaudrap
4,683830
answered 3 hours ago
Niel de Beaudrap
4,683830
4,683830
add a comment |Â
add a comment |Â
BlueLagoon is a new contributor. Be nice, and check out our Code of Conduct.
BlueLagoon is a new contributor. Be nice, and check out our Code of Conduct.
BlueLagoon is a new contributor. Be nice, and check out our Code of Conduct.
BlueLagoon is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4371%2frelation-between-qma-and-pqma%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password