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?


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:

  1. If $x \in L$ then $\Pr[T(x) = 1] \geq 2/3$.
  2. 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 — 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.


Your Answer

