1
$\begingroup$

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?

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't understand...what do you mean by "value of the oracle"? I used to think it means getting the right path in the non-deterministic case. It might make sense for Probabilistic T.M.s in the same sense but I that's all that I can understand but you are saying it has nothing to do with non-determinism. So I don't understand what you want to say. $\endgroup$
    – User Not Found
    Jun 26, 2017 at 14:29
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Jun 26, 2017 at 15:25
  • $\begingroup$ I suggest reviewing the definition of oracle Turing machines in the classical case. See for example Wikipedia. $\endgroup$
    – Yuval Filmus
    Jun 26, 2017 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.