What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?

Question

In these notes about quantum computation by Scott Aronson, he explains that the computation classes $\mathsf{BPP}$ is contained in $\mathsf{BQP}$, but that they are not equal, and

So, the bottom line is that we get a problem -- Simon's problem -- that quantum computers can provably solve exponentially faster than classical computers. Admittedly, this problem is rather contrived, relying as it does on a mythical "black box" for computing a function f with a certain global symmetry. Because of its black-box formulation, Simon's problem certainly doesn't prove that $\mathsf{BPP} \neq \mathsf{BQP}$. What it does prove that there exists an oracle relative to which $\mathsf{BPP} \neq \mathsf{BQP}$. This is what I meant by formal evidence that quantum computers are more powerful than classical ones.

What does he mean by an oracle separation?

My understanding of an oracle for a Turing machine is one that solves the halting problem. Surely that can't be the case here?

Answer 1

No, an oracle is a black box that solves a problem in a single step. The problem that it solves can be any problem, it doesn't need to be the halting problem.

What Scott is saying is that there is some black box that a BQP machine with it can do more than what a BPP machine can do with it. However, it doesn't mean that without that black box BQP is more powerful than BPP.

A simpler case is P vs. NP. By Baker, Gill, and Solovay's result there is a black box that P with that black box is not equal to NP with that black box. But it doesn't tell us much about what should be the answer to P vs. NP.

Answer 2

An oracle is just a theoretical device which will provide the answer to a given class of decision problems in a single step. We say that a decision problem is in $BPP$ relative to the oracle if a turing machine (or whatever model of computation you are using) with access to the oracle can answer the decision problem in a polynomial amount of time with bounded probability of error. Similarly, a problem is in $BQP$ relative to the oracle if a quantum turing machine with access to the oracle can answer the decision problem in a polynomial amount of time with bounded probability of error.

This is closely related to the notion of oracle you know. An oracle which can solve the halting problem is a (very powerful) example of an oracle. Usually when one is talking about such an oracle, one wants to know what problems are in $R$ relative to the oracle, i.e. are computable by a turing machine with access to the oracle.

Answer 3

It depends.

If $\mathrm{BPP} = \mathrm{BQP} = \mathrm{EXP} = \mathrm{EXP}^\mathrm{NP}$, then any oracle separation result would necessarily go beyond $\mathrm{ELEMENTARY} = \cup_{k} k-\mathrm{EXP}$.

Indeed, $\mathrm{BPP}^\mathrm{EXP} = \mathrm{BQP}^\mathrm{EXP} = \mathrm{PP}^\mathrm{EXP} = \mathrm{EXP}$. Going further, we also have $\mathrm{BPP}^\mathrm{EEXP} = \mathrm{BQP}^\mathrm{EEXP} = \mathrm{PP}^\mathrm{EEXP} = \mathrm{EEXP}$. And so on, and on, ad astra.

So, with current mathematical arsenal, we can only hope to construct a separating oracle with at least some non-elementary logic.

On the other hand, if $\mathrm{BPP} \neq \mathrm{BQP}$ holds, then a trivial separating oracle exists, namely $\emptyset$.