Consequences of $NP\subseteq P/poly$ to $BQP$

Question

A post here 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$?

Answer 1

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 2

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), and even to $\mathsf{O_2 P}$ (Chakaravarthy-Roy, STACS 2006). 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).

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