<p>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.</p>

<p>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 <a href="http://arxiv.org/abs/quant-ph/9701001" rel="nofollow">quant-ph/9701001</a>). </p>

<p>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 <a href="http://www.scottaaronson.com/papers/bqpph.pdf" rel="nofollow">BQP and the polynomial hierarchy</a> for example).</p>

CC BY-SA 3.0
2011-08-20T18:37:58.140Z
(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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-21T03:56:35.050Z
@Tsuyoshi: Both good points. I've clarified the language now.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-21T04:09:52.173Z
What's with the downvotes without comments?
Joe Fitzsimons
CC BY-SA 3.0
2011-08-21T06:07:55.820Z
@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.
Kaveh
CC BY-SA 3.0
2011-08-21T06:24:16.683Z
@Kaveh: I'm not sure what you are refering to when you say "As in Dana's answer case". Which question/answer is that?
Joe Fitzsimons
CC BY-SA 3.0
2011-08-21T07:26:16.487Z
@Joe, [this one](http://cstheory.stackexchange.com/questions/7728/multiplication-of-normal-distributions/7729#7729).
Kaveh
CC BY-SA 3.0
2011-08-21T18:04:20.410Z
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.
Alessandro Cosentino
CC BY-SA 3.0
2011-08-20T14:19:05.943Z
2011-08-21T03:55:58.110Z
2011-08-21T03:55:58.110Z
Joe Fitzsimons
<p>What is the relation between BQP complexity class and P and NP?</p>

CC BY-SA 3.0
2011-08-20T12:57:05.373Z
I want to know it, too.  I also want to know the relation between P and NP.  Voted to close as off topic.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-20T13:24:21.303Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-20T13:27:25.777Z
Doesn't Wikipedia answer this? http://en.m.wikipedia.org/wiki/BQP
Aaron Sterling
CC BY-SA 3.0
2011-08-20T16:14:53.337Z
I agree: "wikipedia has the answer" is a good reason to close the question. Unfortunately, Joe already answered it :)
Suresh Venkat
CC BY-SA 3.0
2011-08-20T17:53:42.297Z
This is definitely off-topic here and should be closed. @Amir, please read the FAQ, and next time check the [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo) or Wikipedia if you want to know the relation between complexity classes.
Kaveh
CC BY-SA 3.0
2011-08-21T05:32:52.740Z
@Suresh: Sorry!
Joe Fitzsimons
CC BY-SA 3.0
2011-08-21T06:11:34.973Z
I suggest migrating the question and Joe's answer to Math.SE.
Kaveh
CC BY-SA 3.0
2011-08-21T06:18:19.237Z
@Kaveh: Sure. I don't have a math.SE account, so if you can migrate it, please do.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-21T07:20:11.613Z
Not sure why we should migrate. why not just close ?
Suresh Venkat
CC BY-SA 3.0
2011-08-21T07:28:11.617Z
@Suresh, I started a meta discussion on [when we should migrate and when we should simply close](http://meta.cstheory.stackexchange.com/questions/1285/to-migrate-or-not-to-migrate-just-close).
Kaveh
CC BY-SA 3.0
2011-08-21T17:15:06.537Z
@Kaveh would this question be on-topic at math.SE? Do they allow questions that can be easily checked on Wikipedia? We might want to check with them before migrating.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-21T17:21:06.653Z
@Artem, AFAIK they don't have such restrictions.
Kaveh
CC BY-SA 3.0
2011-08-21T22:19:34.513Z
math.SE allows simple questions, even homework.
chazisop
<cc.complexity-theory><quantum-computing>
Quantum complexity class vs classical complexity class
amir amir
# Quantum complexity class vs classical complexity class

(Asked by: username_0 on 2011-08-20)

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

**Tags:** cc.complexity-theory, quantum-computing
> **Comments:**
> **username_1**: I want to know it, too.  I also want to know the relation between P and NP.  Voted to close as off topic.  
> **username_1**: 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.  
> **username_2**: Doesn't Wikipedia answer this? http://en.m.wikipedia.org/wiki/BQP  
> **username_3**: I agree: "wikipedia has the answer" is a good reason to close the question. Unfortunately, Joe already answered it :)  
> **username_4**: This is definitely off-topic here and should be closed. @Amir, please read the FAQ, and next time check the [Complexity Zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo) or Wikipedia if you want to know the relation between complexity classes.  
> **username_5**: @Suresh: Sorry!  
> **username_4**: I suggest migrating the question and Joe's answer to Math.SE.  
> **username_5**: @Kaveh: Sure. I don't have a math.SE account, so if you can migrate it, please do.  
> **username_3**: Not sure why we should migrate. why not just close ?  
> **username_4**: @Suresh, I started a meta discussion on [when we should migrate and when we should simply close](http://meta.cstheory.stackexchange.com/questions/1285/to-migrate-or-not-to-migrate-just-close).  
> **username_6**: @Kaveh would this question be on-topic at math.SE? Do they allow questions that can be easily checked on Wikipedia? We might want to check with them before migrating.  
> **username_4**: @Artem, AFAIK they don't have such restrictions.  
> **username_7**: math.SE allows simple questions, even homework.  

---

## 1 answers

### Answer by username_5 on 2011-08-20. Score: 4

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](http://arxiv.org/abs/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](http://www.scottaaronson.com/papers/bqpph.pdf) for example).

> **Comments:**
> **username_1**: (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.  
> **username_5**: @Tsuyoshi: Both good points. I've clarified the language now.  
> **username_5**: What's with the downvotes without comments?  
> **username_4**: @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.  
> **username_5**: @Kaveh: I'm not sure what you are refering to when you say "As in Dana's answer case". Which question/answer is that?  
> **username_4**: @Joe, [this one](http://cstheory.stackexchange.com/questions/7728/multiplication-of-normal-distributions/7729#7729).  
> **username_8**: 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.  

---

