BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$

Question

I am a complexity beginner, actually a quantum physicist.

In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of BosonSampling exactly, would result in the collapse of the Polynomial Hierarchy.

If you are not familiar with BosonSampling or any quantum physics at all, do not bother, it won't be necessary for this question: I am interested in one particular aspect of the argument, that I do not understand because of my lack of background: It seems to have to do with the relation of function/search problems and corresponding(?) decision problems.

Specifically, on page 33, in the the proof of Theorem 1, they show that a #$P$-hard problem is also contained $FBPP^{{NP}^{\mathcal{O}}}$ where $\mathcal{O}$ is an oracle to some problem called BosonSampling. From there, they immediately seem to get that $$P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$$

My question is: How? I understand that there is a difference between counting/function problem complexity classes like $\#P$ or $FBPP$ and classes for decision problems. But how to relate the results? In particular, why is it $P^{\#P}$ on the left?

Answer 1

I'm not an expert, and I have one blank space in my answer, hope someone might fill it in.

$FBPP$ is the class of search problems $R = (B_x)_{x\in\{0,1\}^*}$ for which there exists a probabilistic polynomial-time algorithm $A$ that, given $\langle x, 0^ {1/\varepsilon}\rangle$ as input, produces an output $y$ such that $Pr [y \in B_x] ≥ 1 − \varepsilon$, where the probability is over $A$’s internal randomness.

Suppose that $L$ is a $\# P-$hard problem, and $L \in FBPP^{NP^{\mathcal{O}}}$. Then, $$P^{\# P} \subseteq P^{L} \subseteq P^{FBPP^{NP^{\mathcal{O}}}} \subseteq BPP^{NP^{\mathcal{O}}}$$

The second inclusion is clear. The first inclusion: suppose $L_1 \in P^{\# P}$. It means that there exists some polynomial algorithm $\mathcal{A}$ which makes queries to some functions $f_1, f_2, \ldots$ from $\#P$. By the definition of $\#P-$hard problems, $f_i \in FP^{L}$, where $FP$ is the class of polynomially computed functions $f:\{0,1\}^*\rightarrow \{0,1\}^*$. It means that every $\mathcal{A}$'s query to $f_1, f_2, \ldots$ can be replaced by a polynomial program with (at most polynomial) number of queries to $L$, or simply speaking $\mathcal{A}$ is equivalent to some polynomial program $\mathcal{B}$ with queries to $L$. We've shown $$P^{\#P} \subseteq P^{FP^{L}} = P^L$$ We see that $P^{FP}$ can be replaced by $P$.

The third inclusion: again, the same trick: here $P^{FBPP}$ turns to $BPP$. Suppose $L_2 \in P^{FBPP^{NP^{\mathcal{O}}}}$ and $\mathcal{A}$ is the corresponding algorithm for $L_2$. $\mathcal{A}$ makes at most $p(n)$ queries to the probabilistic polynomial programs $A_1, A_2, \ldots$ which solve some search problems. $\mathcal{A}$ uses randomness, but always gives the right answer. One can supposedly make $A_1, A_2\ldots $ a part of $\mathcal{A}$; the resulting probabilistic polynomial algorithm $B$ with queries to $NP^{\mathcal{O}}$ never errs and belongs to $BPP^{NP^{\mathcal{O}}}$.

The only doubt that I have here is that there might be a polynomial number of queries to different functions $FBPP$, and $\mathcal{B}$ is supposed to know all the algorithms for them. It is widely known that if $\mathcal{C}$ is a complexity class with a complete problem $\mathcal{L}$, then $A^{\mathcal{L}} = A^{C}$ for class $P$. However, $BPP$ doesn't have complete problems, and I'm not sure about $FBPP$.