Basic complexity theory (in Oracle Separation of BQP and PH)

I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$ ^O\nsubseteq$ PH$ ^O$ . Aaronsons paper was helpful, but I still have some questions left.

  1. Raz and Tal derive Corollary 1.5 from 1.4 “by the relation between black-box separations and oracle separations”, but aren’t those the same thing? I thought the following all mean the same:

    • black-box model
    • oracle model
    • relative/relativized problem
    • query complexity

    It would make more sense to me if Corollary 1.5 follows from 1.4 by the relation between promise problems and decision problems in the black-box model.

  2. I am not sure how to interpret the fact that there is randomness in the problem. I think of a class such as BPP as languages solvable by a regular Turing machine with access to a random tape, which can make an error with a constant probability over its random bits. However we need to consider the worst case instantiation of the problem (right?). For a language to be in PH, there needs to be a PH-machine (without access to randomness) that does not fail on any input. Now for any oracle-output coming from one distribution there is a non-zero probability that it was actually generated by the other distribution, so the PH-machine will be wrong sometimes. Why is that argument not sufficient to show that the problem is not in PH (or any other “zero-error” class for that matter)?

  3. What exactly is meant by an AC$ ^0$ circuit with access to an oracle? I’ve seen this described as “a circuit with access to the oracle’s truth table”, which I could understand if the oracle solved a decision problem $ f: \{0,1\}^n \rightarrow \{0,1\}$ , then the circuit input nodes are $ x_i = f(i)$ for $ i \leq 2^n$ . However, here the oracle samples from one of two distributions on $ \{\pm 1\}^{2N}$ and the circuit is defined as $ A: \{\pm 1\}^{2N} \rightarrow \{\pm 1\}$ . Does that mean the circuit only gets access to a single query output?