What exactly is an oracle?

What exactly is an "oracle"? Wikipedia says that an oracle is a "blackbox", but I'm not sure what that means.

For example, in the Deutsch–Jozsa algorithm,
$$\hspace{85px}$$,
is the oracle just the box labeled $$ U_f " ,$$ or is it everything between the measurement and the inputs (including the Hadamard gates)?

And to give the oracle, do I need to write $$U_f$$ in matrix form or the condensed form: $$U_f$$ gives $$y \rightarrow y \oplus f(x)$$ and $$x \rightarrow x$$ is enough with respect to the definition of an oracle?

An oracle (at least in this context) is simply an operation that has some property that you don't know, and are trying to find out. The term "black box" is used equivalently, to convey the idea that it's just a box that you can't see inside, and hence you don't know what it's doing. All you know is that you can supply inputs and receive outputs. In the circuit diagram you depict, it is just the $$U_f$$ box. Everything else is stuff that you are adding in order order to help interrogate the oracle and discover its properties.

To give the oracle, you can write it in any valid form that defines a map from all possible inputs to outputs. This could be a matrix (presumably with an unknown parameter), or it could be the map $$U:(x,y)\mapsto (x,y\oplus f(x))$$ (strictly, $$\forall x,y\in\{0,1\}$$), because given either description, you can work out the other.

• Could you clarify what you meant by strictly in the last sentence? – Aritra Das Mar 26 '19 at 12:36
• @tparker not really - the purpose of such oracle forms is often that it allows a description not only of the algorithm, but for optimality of the algorithm. That is measured simply as a count of the number of uses of the oracle. It doesn’t matter how long the oracle takes to run. So for grover’s, that requires square root of the number of oracle calls that the classical one does. – DaftWullie Oct 2 '19 at 5:28
• You're right; my comment was poorly phrased. What I meant to say is that if you want an oracle result to give any insight into a "real-world" runtime, you need to assume (in addition to the black-box assumption) that whatever subroutine you're running to actually implement the oracle call dominates the algorithm's runtime, so that the number of oracle calls is indeed proportional to the actual runtime. But that's an addition assumption for "real-world" relevance, not a necessary part of the definition of an oracle. – tparker Oct 2 '19 at 11:57