21
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – Martin Schwarz
    Jan 14, 2013 at 12:37
  • 1
    $\begingroup$ 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! :) ) $\endgroup$
    – Scott Aaronson
    Jan 14, 2013 at 13:41
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Emil Jeřábek
    Aug 9, 2014 at 21:19
  • 1
    $\begingroup$ (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.) $\endgroup$
    – Emil Jeřábek
    Aug 9, 2014 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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