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?
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.