patternModerate
What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?
Viewed 0 times
mathsfmeantbqpwhatbppbetweenclassesandoracleseparation
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#13528, answer score: 15
Revisions (0)
No revisions yet.