What is the relation between BQP complexity class and P and NP?
$\begingroup$
$\endgroup$
13
-
10$\begingroup$ I want to know it, too. I also want to know the relation between P and NP. Voted to close as off topic. $\endgroup$– Tsuyoshi ItoAug 20, 2011 at 12:57
-
1$\begingroup$ On second thought, I think that the question can become suitable here on cstheory.stackexchange.com if you broaden the question to make it answerable (and remove the obvious part). But in its current form, it is off topic on cstheory. $\endgroup$– Tsuyoshi ItoAug 20, 2011 at 13:24
-
4$\begingroup$ Doesn't Wikipedia answer this? en.m.wikipedia.org/wiki/BQP $\endgroup$– Aaron SterlingAug 20, 2011 at 13:27
-
$\begingroup$ I agree: "wikipedia has the answer" is a good reason to close the question. Unfortunately, Joe already answered it :) $\endgroup$– Suresh VenkatAug 20, 2011 at 16:14
-
2$\begingroup$ This is definitely off-topic here and should be closed. @Amir, please read the FAQ, and next time check the Complexity Zoo or Wikipedia if you want to know the relation between complexity classes. $\endgroup$– KavehAug 20, 2011 at 17:53
|
Show 8 more comments
1 Answer
$\begingroup$
$\endgroup$
7
P is contained within BQP. This is trivial, since quantum operations are a superset of classical operations. Indeed, BQP contains BPP as well, since you can use Hadamards to produce randomness in the computational basis.
Much less trivial is the relationship between NP and BQP. At present, the consensus opinion seems to be that neither entirely contains the other, though clearly both contain P, and certain problems believed to be NP-intermediate like factoring integers, so their intersection is itself non-trivial. There are oracles relative to which BQP is not contained within NP (via recursive Fourier sampling for example), and conversely oracles relative to which NP is not contained within BQP (this is true with probability 1 relative to a random oracle, see quant-ph/9701001).
We do know that BQP is contained within PP, but there is strong evidence that it is not contained within the polynomial hierarchy at all (see Scott Aaronson's paper on BQP and the polynomial hierarchy for example).
-
1$\begingroup$ (1) “Strictly contain” is often used as a synonym for “properly contain” (⊋), and it is better to avoid that wording here. (2) “NP-intermediate” is a little misleading here, because factoring is not known to be NP-intermediate even assuming P≠NP. It is even possible that P=BQP⊊NP, although that would be surprising. $\endgroup$ Aug 20, 2011 at 18:37
-
$\begingroup$ @Tsuyoshi: Both good points. I've clarified the language now. $\endgroup$ Aug 21, 2011 at 3:56
-
2$\begingroup$ What's with the downvotes without comments? $\endgroup$ Aug 21, 2011 at 4:09
-
6$\begingroup$ @Joe, I guess they are objecting to you answering the question (As in Dana's answer case). @ down voters: we have discussed it many times and no one has ever objected so down voting without commenting is not constructive! So please when down voting leave a comment explaining the reason for the down vote. Also although this question is off-topic, it is not a homework question and AFAIK it is at least unusual to down vote it. $\endgroup$– KavehAug 21, 2011 at 6:07
-
3$\begingroup$ I did down-vote for those reasons listed as comments in the Dana's answer pointed by Kaveh. Nothing against the answer itself. I just believe that it would have been more correct to not ignore Tsuyoshi's and Aaron's comments, reply to them and then post your answer. $\endgroup$ Aug 21, 2011 at 18:04