What is the relation between BQP complexity class and P and NP?


closed as off topic by Kaveh Nov 25 '12 at 18:07

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 Ito Aug 20 '11 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 Ito Aug 20 '11 at 13:24
  • 4
    $\begingroup$ Doesn't Wikipedia answer this? en.m.wikipedia.org/wiki/BQP $\endgroup$ – Aaron Sterling Aug 20 '11 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 Venkat Aug 20 '11 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$ – Kaveh Aug 20 '11 at 17:53

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$ – Tsuyoshi Ito Aug 20 '11 at 18:37
  • $\begingroup$ @Tsuyoshi: Both good points. I've clarified the language now. $\endgroup$ – Joe Fitzsimons Aug 21 '11 at 3:56
  • 2
    $\begingroup$ What's with the downvotes without comments? $\endgroup$ – Joe Fitzsimons Aug 21 '11 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$ – Kaveh Aug 21 '11 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$ – Alessandro Cosentino Aug 21 '11 at 18:04

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