Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from mathoverflow.net Jul 31 '13 at 0:56

This question came from our site for professional mathematicians.

1  
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.