<p>If $\mathsf{NP} \subseteq \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma_2 P}$ (Karp-Lipton), and in fact to $\mathsf{S_2 P}$ (attributed to Sengupta by <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2001.959938">Cai, FOCS 2001</a>), and even to $\mathsf{O_2 P}$ (<a href="http://www.cs.wisc.edu/~venkat/o2.ps">Chakaravarthy-Roy, STACS 2006</a>). Note that one cannot go too much further than this with relativizing techniques, since already $\mathsf{S_2 P} \subseteq \mathsf{ZPP}^{\mathsf{NP}}$ (Cai, 2001, ibid), yet there are oracles where $\mathsf{NP} \subseteq \mathsf{P/poly}$ but $\mathsf{PH} \neq \mathsf{P}^{\mathsf{NP}}$ (<a href="http://dx.doi.org/10.1016/S0019-9958(86)80012-2">Heller, 1986</a>). </p>

<p>(Someone more knowledgable in quantum would have to answer if/how this affects $\mathsf{BQP}$.)</p>

CC BY-SA 3.0
2015-12-29T06:49:35.883Z
do you know about http://cs.stackexchange.com/questions/51196/when-can-arguments-for-mathsfnp-be-replaced-by-mathsfnexp-by-employing?
Turbo
CC BY-SA 3.0
2015-11-27T18:46:35.033Z
2015-11-27T18:46:35.033Z
Joshua Grochow
<p>I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$.  Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more impressive with just good old classical nonuniformity than we could with quantum mechanics.  And it would imply $NP\subset BQP/poly$. :-)  OK, it would also weaken the arguments that BosonSampling, and other quantum sampling tasks of that kind, are classically hard.  For those arguments involve showing that if the sampling tasks can be done in classical polynomial time, then $PH$ collapses to the second or third level (along with several other strange things, like $P^{\#P}=BPP^{NP}$).  But if $NP\subset P/poly$, then $PH$ collapses anyway.</p>

CC BY-SA 3.0
2015-11-30T03:04:35.547Z
2015-11-30T03:04:35.547Z
Scott Aaronson
<p>A post here <a href="https://cstheory.stackexchange.com/questions/15066/consequences-of-bqp-subseteq-p-poly">Consequences of $BQP \subseteq P/poly$?</a> queried on Consequences of $BQP \subseteq P/poly$.</p>

<p>It is not known if $NP\subseteq BQP$.</p>

<p>In general, what are the consequences of $NP\subseteq P/poly$?</p>

<p>How does $NP\subseteq P/poly$ affect $BQP$?</p>

<cc.complexity-theory><complexity-classes><quantum-computing><circuit-complexity><big-picture>
Consequences of $NP\subseteq P/poly$ to $BQP$
Turbo
# Consequences of $NP\subseteq P/poly$ to $BQP$

(Asked by: username_0 on 2015-11-27)

A post here [Consequences of $BQP \subseteq P/poly$?](https://cstheory.stackexchange.com/questions/15066/consequences-of-bqp-subseteq-p-poly) queried on Consequences of $BQP \subseteq P/poly$.

It is not known if $NP\subseteq BQP$.

In general, what are the consequences of $NP\subseteq P/poly$?

How does $NP\subseteq P/poly$ affect $BQP$?

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, circuit-complexity, big-picture


---

## 2 answers

### Answer by username_2 on 2015-11-30. Score: 10 | Accepted answer

I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$. Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more impressive with just good old classical nonuniformity than we could with quantum mechanics. And it would imply $NP\subset BQP/poly$. :-) OK, it would also weaken the arguments that BosonSampling, and other quantum sampling tasks of that kind, are classically hard. For those arguments involve showing that if the sampling tasks can be done in classical polynomial time, then $PH$ collapses to the second or third level (along with several other strange things, like $P^{\#P}=BPP^{NP}$). But if $NP\subset P/poly$, then $PH$ collapses anyway.


---

### Answer by username_1 on 2015-11-27. Score: 9

If $\mathsf{NP} \subseteq \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma\_2 P}$ (Karp-Lipton), and in fact to $\mathsf{S\_2 P}$ (attributed to Sengupta by [Cai, FOCS 2001](http://doi.ieeecomputersociety.org/10.1109/SFCS.2001.959938)), and even to $\mathsf{O\_2 P}$ ([Chakaravarthy-Roy, STACS 2006](http://www.cs.wisc.edu/~venkat/o2.ps)). Note that one cannot go too much further than this with relativizing techniques, since already $\mathsf{S\_2 P} \subseteq \mathsf{ZPP}^{\mathsf{NP}}$ (Cai, 2001, ibid), yet there are oracles where $\mathsf{NP} \subseteq \mathsf{P/poly}$ but $\mathsf{PH} \neq \mathsf{P}^{\mathsf{NP}}$ ([Heller, 1986](http://dx.doi.org/10.1016/S0019-9958(86)80012-2)).

(Someone more knowledgable in quantum would have to answer if/how this affects $\mathsf{BQP}$.)

> **Comments:**
> **username_0**: do you know about http://cs.stackexchange.com/questions/51196/when-can-arguments-for-mathsfnp-be-replaced-by-mathsfnexp-by-employing?  

---

