Basic complexity theory (in Oracle Separation of BQP and PH)
Let me answer your questions one by one.

Black-box separations versus oracle separations

Black-box algorithms are given access to a black box. For example, an algorithm might get black box access to a function $f\colon \{0,1\}^n \to \{0,1\}$. This means that the algorithm can obtain the value of $f(x)$ for any given $x \in \{0,1\}^n$, but is not otherwise given any explicit description of $f$.

As an example, consider the following promise black box problem: given a function $f$ which is either the constant $0$ or balanced (that is, half its values are $0$ and half are $1$), determine which of these two cases $f$ belongs to. There is a very simple randomized algorithm which makes a constant number of queries and outputs the correct answer with constant probability; but every deterministic algorithm must make exponentially many queries in the worst case. This is an example of a black-box separation between promise versions of $\mathsf{P}$ and $\mathsf{BPP}$.

Oracle separations also pertain to black-box algorithms, but now we want to fix the black box. In order to separate two relativizable complexity classes $A$ and $B$, we need to find a specific oracle $O$ such that $A^O \neq B^O$ (or prove that one exists). For every oracle $O$, the classes $A^O$ and $B^O$ consist of languages decided by algorithms with no auxiliary input. Rather, these algorithms have access to an $O$-oracle. But in contrast to the situation in the preceding paragraph, here the oracle is not part of the input. Rather, it is fixed.

The standard example is Turing machines with access to an oracle to the halting problem. In contrast to the example given above for black-box algorithms, here the oracle is not an input but rather an additional mechanism that the machine can make use of.

On randomness

A language $L$ is in $\mathsf{BPP}$ if there is a randomized polytime machine $T$ such that:


If $x \in L$ then $\Pr[T(x) = 1] \geq 2/3$.
If $x \notin L$ then $\Pr[T(x) = 1] \leq 2/3$.


When considering the black box version of $\mathsf{BPP}$, the definition remains exactly the same. The black box is not randomized; only the algorithm is randomized. As an example, consider the promise problem of determining whether an input black box is the constant zero function or is balanced. This problem can be solved in $\mathsf{BPP}$ by sampling a few points, or in $\mathsf{E}$ by querying the first $2^{n-1}+1$ values of the black box.

Randomization is part of the algorithm, not the decision problem.

Oracle circuits

The paper you are reading doesn't actually use these &mdash; the oracles are only applied to $\mathsf{BQP}$ and $\mathsf{PH}$. But for completeness sake, let me mention that the most common model uses oracle gates, which are gates that provide access to the oracle.

An advice

Let me close with an advice. The paper you are trying to read is at the forefront of research. It would be extremely hard to appreciate it without having some background. This paper is probably not a good entry point into complexity theory. I suggest familiarizing yourself with complexity theory first, for example by reading parts of the textbook by Arora and Barak.