1
$\begingroup$

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:

<span class=$f(x) = 1, \forall x \in \{0,1\}$" />

<span class=$f(x) = \neg x, \forall x \in \{0,1\}$" />

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?

$\endgroup$
2
  • 1
    $\begingroup$ Hi and welcome to QCSE! Have you seen this question and answer? One way I like to think of oracles in the context of the Deutsch-Jozsa (or Simon's) algorithm is adversarially - as if a secret enemy had chosen the oracle and you cannot see what it is. You're right, though, in that if you were able to see the circuit for the oracle then you can know what the oracle itself is, without having to run it. $\endgroup$ Feb 13 at 18:19
  • $\begingroup$ Hi, sorry for the late reply. I've read the answer in your post but I'm still struggling with the concept of "oracle". In the answer it is stated that an oracle is a black-box which has some property we don't know, but are trying to find out. The point is, if I want to implement the oracles for the two functions of my question, actually I'm pretty aware of the properties of the oracles, so where exactly is the "hidden" implementation? Even if the oracle could encode the input and decode the output accordingly to a function, then again, the implementation for different functions is different... $\endgroup$
    – aghin
    Feb 15 at 18:48

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ My impression is that a lot of the misunderstanding stems from the fact that a significant part of the community has a lack of sufficient background in theoretical computer science. $\endgroup$ Feb 19 at 15:43
  • $\begingroup$ @NorbertSchuch certainly. My background is in computer engineering and not (really) in theoretical computer science, much less in physics. I often speak with improper authority about TCS and - even with your help - quickly get tripped up on the physics. But I saw the Stoudenmire and Waintal paper for what it was - clever physicists construing words in a manner different from how they are construed in theoretical computer science. $\endgroup$ Feb 19 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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