<p>I'd say we have no good reason to think BQP is in P/poly.  We do have reasons to think that BQP is <i>not</i> in P/poly, but they're more-or-less identical to our reasons to think that BQP&ne;BPP.  E.g., if BQP&sub;P/poly then Factoring is in P/poly, which is enough to break lots of cryptography according to standard security definitions.</p>

<p>Also, as you correctly point out, there's no quantum analogue of Adleman's trick---indeed, there's no way to "pull the quantumness out of a quantum algorithm," analogous to how one can pull the randomness out of a randomized algorithm.  So I don't think anyone has a guess for what the P/poly advice for simulating a quantum computer should even consist of (any more than they have a guess, say, in the case of NP vs. P/poly).</p>

<p>A final note: my work with Alex Arkhipov (and the independent work of Bremner-Jozsa-Shepherd), can easily be adapted to show that if QUANTUM-SAMPLING is in P/poly (OK, in "BPP-SAMPLING/poly"), then P<sup>#P</sup>&sub;BPP<sup>NP</sup>/poly, and hence the polynomial hierarchy collapses---in this case, I think, to the <i>fourth</i> level.  At present, though, we don't know how to adapt this sort of result from sampling problems to decision problems.</p>

CC BY-SA 3.0
2013-01-14T12:37:35.317Z
Thank you very much for answering, Scott! One thing I'm wondering: what are the known results relating P^#P with levels of PH/poly? What is actually known about P^#P vs. PH/poly? (e.g. is there some non-uniform version of Toda's theorem?). Why would P^#P in PH/poly collapse PH/poly, if we don't know PH/poly in P^#P? Or what am I missing?
Martin Schwarz
CC BY-SA 3.0
2013-01-14T13:41:11.390Z
What one needs to do here is to generalize the proof of the Karp-Lipton Theorem. As a first step, it's not hard to show (using KL-style reasoning) that if coNP is in NP/poly, then PH collapses to the 3rd level. But then that should relativize, to show that if coNP^NP^NP is in NP^NP^NP/poly, then PH collapses to the 5th level. And certainly P^#P in BPP^NP/poly implies coNP^NP^NP is in NP^NP^NP/poly. But hmm, I'm only getting a collapse to the *5th* level here! Assuming this is correct, can anyone improve it to a 4th-level collapse? (If not, it's the "highest" PH collapse I've ever seen! :) )
Scott Aaronson
CC BY-SA 3.0
2014-08-09T21:19:50.083Z
3rd level will do. Both $\mathrm{BPP}\subseteq\mathrm P/\mathrm{poly}$ and Karp–Lipton relativize, so first $\mathrm{BPP}^\mathrm{NP}/\mathrm{poly}=\mathrm{P}^\mathrm{NP}/\mathrm{poly}$, and second, if $\Sigma^P_2\subseteq\mathrm{(BP)P}^\mathrm{NP}/\mathrm{poly}$, then $\Sigma^P_3=\Pi^P_3$.
Emil Jeřábek
CC BY-SA 3.0
2014-08-09T21:45:04.973Z
(And various known strengthenings of KL also relativize for that matter, in particular the assumption above actually collapses PH to $S^P_3\subseteq\mathrm{ZPP^{NP^{NP}}}\subseteq\Sigma^P_3\cap\Pi^P_3$, except I’ve never seen $S^P$ with a subscript other than 2, so it’s likely nonstandard notation.)
Emil Jeřábek
CC BY-SA 3.0
2013-01-13T21:20:44.500Z
2013-01-13T21:20:44.500Z
Scott Aaronson
<p>While <a href="http://en.wikipedia.org/wiki/P/poly#Adleman.27s_theorem">Adleman's theorem</a> shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{poly}$. What complexity-theoretic consequences would such an inclusion have? </p>

<p>Adleman's theorem is <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aP#ppoly">sometimes</a> called "the progenitor of derandomization arguments." $\mathsf{BPP}$ is believed to be derandomizable, whereas there is no evidence that the "quantumness" of $\mathsf{BQP}$ could somehow be removed. Is this possible evidence that $\mathsf{BQP}$ is unlikely to be in $\mathsf{P}/\text{poly}$ ?</p>

<reference-request><quantum-computing><derandomization><conditional-results>
Consequences of $BQP \subseteq P/poly$?
Martin Schwarz
# Consequences of $BQP \subseteq P/poly$?

(Asked by: username_0 on 2013-01-13)

While [Adleman's theorem](http://en.wikipedia.org/wiki/P/poly#Adleman.27s_theorem) shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{poly}$. What complexity-theoretic consequences would such an inclusion have?

Adleman's theorem is [sometimes](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aP#ppoly) called "the progenitor of derandomization arguments." $\mathsf{BPP}$ is believed to be derandomizable, whereas there is no evidence that the "quantumness" of $\mathsf{BQP}$ could somehow be removed. Is this possible evidence that $\mathsf{BQP}$ is unlikely to be in $\mathsf{P}/\text{poly}$ ?

**Tags:** reference-request, quantum-computing, derandomization, conditional-results

---

## 1 answers

### Answer by username_1 on 2013-01-13. Score: 16 | Accepted answer

I'd say we have no good reason to think BQP is in P/poly. We do have reasons to think that BQP is *not* in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP. E.g., if BQP⊂P/poly then Factoring is in P/poly, which is enough to break lots of cryptography according to standard security definitions.

Also, as you correctly point out, there's no quantum analogue of Adleman's trick---indeed, there's no way to "pull the quantumness out of a quantum algorithm," analogous to how one can pull the randomness out of a randomized algorithm. So I don't think anyone has a guess for what the P/poly advice for simulating a quantum computer should even consist of (any more than they have a guess, say, in the case of NP vs. P/poly).

A final note: my work with Alex Arkhipov (and the independent work of Bremner-Jozsa-Shepherd), can easily be adapted to show that if QUANTUM-SAMPLING is in P/poly (OK, in "BPP-SAMPLING/poly"), then P#P⊂BPPNP/poly, and hence the polynomial hierarchy collapses---in this case, I think, to the *fourth* level. At present, though, we don't know how to adapt this sort of result from sampling problems to decision problems.

> **Comments:**
> **username_0**: Thank you very much for answering, Scott! One thing I'm wondering: what are the known results relating P^#P with levels of PH/poly? What is actually known about P^#P vs. PH/poly? (e.g. is there some non-uniform version of Toda's theorem?). Why would P^#P in PH/poly collapse PH/poly, if we don't know PH/poly in P^#P? Or what am I missing?  
> **username_1**: What one needs to do here is to generalize the proof of the Karp-Lipton Theorem. As a first step, it's not hard to show (using KL-style reasoning) that if coNP is in NP/poly, then PH collapses to the 3rd level. But then that should relativize, to show that if coNP^NP^NP is in NP^NP^NP/poly, then PH collapses to the 5th level. And certainly P^#P in BPP^NP/poly implies coNP^NP^NP is in NP^NP^NP/poly. But hmm, I'm only getting a collapse to the *5th* level here! Assuming this is correct, can anyone improve it to a 4th-level collapse? (If not, it's the "highest" PH collapse I've ever seen! :) )  
> **username_2**: 3rd level will do. Both $\mathrm{BPP}\subseteq\mathrm P/\mathrm{poly}$ and Karp–Lipton relativize, so first $\mathrm{BPP}^\mathrm{NP}/\mathrm{poly}=\mathrm{P}^\mathrm{NP}/\mathrm{poly}$, and second, if $\Sigma^P_2\subseteq\mathrm{(BP)P}^\mathrm{NP}/\mathrm{poly}$, then $\Sigma^P_3=\Pi^P_3$.  
> **username_2**: (And various known strengthenings of KL also relativize for that matter, in particular the assumption above actually collapses PH to $S^P_3\subseteq\mathrm{ZPP^{NP^{NP}}}\subseteq\Sigma^P_3\cap\Pi^P_3$, except I’ve never seen $S^P$ with a subscript other than 2, so it’s likely nonstandard notation.)  

---

