33
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
37
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Could you clarify what you meant by strictly in the last sentence? $\endgroup$
    – Aritra Das
    Mar 26, 2019 at 12:36
  • 1
    $\begingroup$ @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. $\endgroup$
    – DaftWullie
    Oct 2, 2019 at 5:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – tparker
    Oct 2, 2019 at 11:57
  • 1
    $\begingroup$ What are oracles used for? Why? $\endgroup$
    – skan
    Apr 12, 2020 at 11:54
  • 2
    $\begingroup$ @skan, think of oracle as an abstraction, like an API call, you do not know how the API is coded, but you know what are its inputs and outputs. By doing this you are abstracting away all the implementation details of the function and hence "the time complexity of the function". By doing this, we will be able to compare the speed of classical algo vs quantum algo. This is the main purpose of oracle. $\endgroup$
    – dhiraj suvarna
    Apr 22, 2021 at 5:00

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.