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?