# What does it mean for a problem to be solved in polynomial time “relative to” an oracle?

I came across the following theorem in page 12 of the following pdf :

There exists an oracle relative to which there is a problem solvable in polynomial time (with bounded error probability) on a quantum computer, but any probabilistic Turing Machine with bounded error probability solving this problem (using the oracle) will require exponential time (at least $2^\frac{n}{2}$ steps on infinitely many inputs (of length n).

My question is what does it mean to say "There exists an oracle relative to which there is a problem". My take on it is that if we try to solve the problem using a non deterministic T.M. or non deterministic Quantum computer (I don't know if such a thing even makes sense as I just started studying Quantum Computing) the oracle is a black box which tells the machine which path to take in the non deterministic step. Is this the correct interpretation?

• I changed your title to a more descriptive one; it also summarizes your question. Does the rearranged sentence maybe even give you the answer? – Raphael Jun 26 '17 at 9:39
• @Raphael Thanks for your help. I believe this supports my thoughts about it which I had written at the end. Am I mistaken? – User Not Found Jun 26 '17 at 9:40
• Let's wait for the experts. – Raphael Jun 26 '17 at 12:11
• Please provide a link to the PDF where you found the theorem. That PDF might contain all the relevant definitions. – Yuval Filmus Jun 26 '17 at 12:28
• @YuvalFilmus www2.fiit.stuba.sk/~kvasnicka/QuantumComputing/Gruska_QC.pdf Page 12 of pdf file. – User Not Found Jun 26 '17 at 14:20

Oracles have nothing to do with non-determinism. They are just a communication mechanism between the algorithm (or Turing machine) and an outside entity, the oracle $O$, which is just a language. In the classical case, the algorithm can query the oracle on a specific input $x$, and it immediately gets the (Boolean) value of the oracle at that input: 1 if $x \in O$, and 0 if $x \notin O$. I'm not quite sure how this works in the quantum case, but perhaps the PDF explains that.
The theorem states that there is some oracle that allows quantum algorithms to solve some problems much faster than classical ones. That is, if a quantum algorithm is given access to this oracle, then it can solve some problem in time Q, but a classical algorithm which is given such access can only solve the problem in time C$\gg$Q.
• The oracle is a language. The value of the oracle at a string $x$ is 1 if $x$ belongs to the language and 0 otherwise. No connection to nondeterminism or probabilistic computation. – Yuval Filmus Jun 26 '17 at 15:25