Implementation of quantum oracles in Deutsch's algorithm

Question

I am studying Deutsch's algorithm (elementary version of Deutsch-Josza) but I'm struggling with the actual implementation of the quantum oracle.

I understand the whole point of the algorithm and what it wants to achieve, i.e. to determine wether a function $f$ is constant or balanced with just one query on the function. However, I don't understand how one must implement the quantum oracle in order to get the algorithm working. We know that a quantum oracle is a black-box function that is used as input to another algorithm; we also know that there are four common functions used for demonstrating the Deutsch's algorithm: constant 1 (constant), constant 0 (constant), negation (balanced) and identity (balanced).

Based on that, take for example the constant 1 and negation: they could be implemented in Qiskit as following:

The first circuit implements the function $f(x) = 1$, whilst the second one the function $f(x) = \neg x$. What I don't understand is why the oracles (middle part of each circuit, wrapped by H gates) are different. If the oracle is a black-box function, it seems to me that it isn't so much black-box, as we need to know how to implement it based on the function we want to evaluate. Rather than understanding the algorithm itself, it seems that one must understand how to create the oracle, so what if we want to evaluate a more complex function?

Last but not least, if we look at $f(x) = 1, \forall x \in \{0,1\}$, we already know it is a constant function (same for $f(x) = \neg x, \forall x \in \{0,1\}$, we know at priori that it is a balanced function), so what is the point of creating an oracle and running it through Deutsch's algorithm?

score 2 · Answer 1 · answered Feb 16 '24 at 14:01

^{Marked CW}

Because "whence oracles" is such a commonly asked question, this suggests, to me at least, the community struggles with properly motivating their use and study. For example, a recent paper generated a lengthy conversation on the use (and misuse) of the concept. Even Terry Tao entered the fray a while ago.

One way to think of oracles would be that "if we cannot instantiate the oracle ourselves and must accept that another party, even adversarially, will put it into the circuit for us, then how many times do we need to run the circuit before we learn the question posed?" That first "if" is a big one to get your head around, but by accepting it as a premise, the "then" clause is really where the magic lies - in Deutsch, in Deutsch-Jozsa, in Bernstein-Vazirani, in Simon, in Grover. Even Shor's algorithm can be thought of as instantiating an oracle for determining the period of a periodic function.

To address your question in particular, yes by instantiating the oracle yourself you know whether your function is balanced or constant. But you have to imagine a world where you don't have access to the oracle yourself, and that it be given to you from the outside.

^{Deutsch originally motivated his algorithm by envisioning a program to predict tomorrow's stock-market, and knowing whether an investment strategy is balanced or constant would help in the prediction - he fancifully said that sometimes we could get our investment strategy with a single call to the oracle - but this is more of an historical aside, and it was other computer scientists who recognized Deutsch as providing an improved oracle program.}

Implementation of quantum oracles in Deutsch's algorithm

1 Answers1