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?