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

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?

## migrated from mathoverflow.netJul 31 '13 at 0:56

This question came from our site for professional mathematicians.

• He means these classes can be separated relative to a certain oracle (see en.wikipedia.org/wiki/Oracle_machine); in this case the oracle is the "black box" Wikipedia describes here en.wikipedia.org/wiki/Simon%27s_problem. At any rate, this seems too elementary for this site. – Sam Hopkins Jul 30 '13 at 23:58
• @sam convert to answer? – Ran G. Jul 31 '13 at 1:40

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.