Why do black box separations imply oracle separations?

Question

Why does Simon's algorithm show that there exists an oracle $O$ such that $\mathsf{BPP}^O$ is not equal to $\mathsf{BQP}^O$?

To show that $\mathsf{BQP}^O$ is larger than $\mathsf{BPP}^O$, one needs to find a language $L$ in $\mathsf{BQP}^O$ that is not in $\mathsf{BPP}^O$. For the case of Simon's problem showing this separation, what is $O$ and what is $L$?

Simon's problem is an example of a problem where the quantum algorithm takes exponentially fewer queries than all possible classical algorithms. This gives a black box separation (i.e. a query separation) between $\mathsf{BPP}$ and $\mathsf{BQP}$. But how does this imply an oracle separation between $\mathsf{BPP}$ and $\mathsf{BQP}$?

Answer 1

Oracle separations and black-box separations are effectively synonymous.

Simon didn't give any specific language $L$ that can be solved more efficiently on a quantum computer than on a classical computer, because he did not, in particular, instantiate his this by applying it to a language that satisfies his promise. Rather, he gave a class of languages $O$, and showed that, relative to this class, $\mathsf{BPP}^O\ne\mathsf{BQP}^O$.

We say "in the black-box setting, a quantum computer needs fewer oracle calls than a classical computer to solve an instance of Simon's problem." We don't yet have a particular instance of a language that is in Simon's class of languages - that satisfies Simon's promise -because we don't know how to instantiate it concretely, even after ~30 years.

Answer 2

From Footnote 1 in the paper you mentioned in your comment (Oracle Separation of BQP and PH by Raz and Tal)

In our entire discussion of black-box complexity classes, we consider complexity classes of promise problems, rather than decision problems. Nevertheless, separations of classes of promise problems in the black-box model imply oracle separations of the corresponding classes of decision problems in the “real” world

The footnote then refers to Aaronson's paper BQP and the polynomial hierarchy which says:

We should clarify that there are two questions here: whether $\mathsf{BQP} \subseteq \mathsf{PH}$ and whether $\mathsf{PromiseBQP} \subseteq \mathsf{PromisePH}$. In the unrelativized world, it is entirely possible that quantum computers can solve promise problems outside the polynomial hierarchy, but that all languages in $\mathsf{BQP}$ are nevertheless in $\mathsf{PH}$. However, for the specific purpose of constructing an oracle $A$ such that $\mathsf{BQP}^A \not \subset \mathsf{PH}^A$, the two questions are equivalent, basically because one can always “offload” a promise into the construction of the oracle $A$.

Then he gave a proof for this claim.

You can find a related discussion in the comments under this blogpost: https://scottaaronson.blog/?p=451 (comments #21-23)