Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

While Adleman's 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 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}$ ?

share|cite|improve this question
up vote 13 down vote accepted

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.

share|cite|improve this answer
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 Jan 14 '13 at 12:37
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 Jan 14 '13 at 13:41
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 Aug 9 '14 at 21:19
(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 Aug 9 '14 at 21:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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