# 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?