Let $\mathscr{F}$ be the collection of all functions $F:\{0,1\}^*\rightarrow\{0,1\}^*$, such that for every $n$, the restriction $F_n:=F|_{\{0,1\}^n}$ (restriction of $F$ on $\{0,1\}^n$) satisfies the promise of Simon's problem. For each $F\in\mathscr{F}$, let $L(F)\subseteq\{0\}^*$ be the unary language
$$L(F)=\{0^n\mid F_n\textrm{ is injective}\}.$$
We have:
- For every $F\in\mathscr{F}$, $L(F)\in\mathsf{BQP}^F$. This is because to decide if $x\in L(F)$, we can first check if $x=0^n$ for some $n$, and if so, we apply Simon's algorithm to decide if $F_n$ is injective, with bounded error (Since the $\mathsf{BQP}$ machine has oracle access to $F$, it just creates the uniform superposition over $\{0,1\}^n$ to make queries to $F_n$).
- There exists $F\in\mathscr{F}$ such that $L(F)\notin\mathsf{BPP}^F$. At a high level, this is proved by diagonalization, due to the fact that $\mathscr{F}$ is uncountable while the set of $\mathsf{BPP}$ oracle machines is countable. In detail, the proof goes as follows.
We enumerate polynomial-time probablistic oracle Turing machines as
$$\mathcal{M}_1,\mathcal{M}_2,\ldots,\mathcal{M}_i,\ldots$$
and construct our $F$ while enumerating them. Starting from $\mathcal{M}_1$, and suppose it has time bound $p_1(n)=\mathrm{poly}(n)$. That means on input $0^n$, it only makes oracle queries on strings of length at most $p_1(n)$. We claim the following (because of the classical query lower bound on Simon's problem):
There exist $n\in\mathbb{N}$, and $F_1,\ldots,F_{p_1(n)}$, such that $\mathcal{M}_1$ does NOT give the correct answer on $0^n$
(That is, it rejects with probability at least $1/3$ in case that $F_n$ is injective, and vice versa).
Generally, if at $\mathcal{M}_i$ (with time bound $p_i(n)$) we already fixed $F_1,\ldots,F_N$, then
There exist $n>N$, and $F_{N+1},\ldots,F_{p_i(n)}$, such that $\mathcal{M}_i$ does NOT give the correct answer on $0^n$.
This is because if not, we can always hardwire $F_1,\ldots,F_N$, and brute force every function on at most $N$ bits, to get a classical query algorithm for Simon's problem with $p_i(n)+O(1)$ queries, which violates the $2^{\Omega(n)}$ classical query lower bound.
In the end, we obatin a function $F\in\mathscr{F}$ such that every $\mathcal{M}_i$, when calling the oracle $F$, is at some point incorrect in deciding $L(F)$. Therefore $L(F)\notin\mathsf{BPP}^F$, and $F$ is an oracle such that $\mathsf{BQP}^F\neq \mathsf{BPP}^F$.
Finally, it is easy to convert $F$ into a function $O$ with one-bit output if you insist on $O$ being a language. Just let $O(x,i)=F(x)_i$, and any oracle machine calling $F$ can be modified into one calling $O$ and vice versa, with polynomial overhead. Therefore we also have $\mathsf{BQP}^O\neq \mathsf{BPP}^O$.
I believe the above argument is pretty standard for proving oracle separations, which is why it was often omitted. If you are interested, you can also read the oracle separation between $\mathsf{BQP}$ and $\mathsf{PH}$ by Raz and Tal, where at the end of the proof they used the same argument, in a probabilistic fashion.
