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?

up vote 14 down vote accepted

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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