22

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}$ ?

András Salamon
  • 19,000
  • 3
  • 64
  • 150
Martin Schwarz
  • 5,496
  • 25
  • 41

1 Answers1

15

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.

Scott Aaronson
  • 13,733
  • 2
  • 62
  • 68
  • 2
    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
  • 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! :) ) – Scott Aaronson Jan 14 '13 at 13:41
  • 1
    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 09 '14 at 21:19
  • 1
    (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 09 '14 at 21:45