There is something I really misunderstand about the Deutsch-Jozsa algorithm.

To check if $f$ is balanced or constant, we use the following algorithm :

enter image description here

Where $U_f$ gives $(x,y) \rightarrow (x, y \oplus f(x))$.

Let's take $n=1$ for simplicity (thus the function $f$ is defined on $(0,1)$).

We have $4$ possible $U_f$ associated to $2$ constants possibility ($f$ equal to $0$ or $1$), and two balanced possibilities.

So, in practice, if I want to implement this in a circuit, I have to know exactly the "matrix" of $U_f$. And to do it I have to compute $f$ $2$ times. Thus, I know if $f$ is balanced or constant even before having applied the quantum algorithm. So for a practical aspect, I don't understand what is the point of this.

Said differently, if I am given $U_f$ I agree that in $1$ step I will know if $f$ is balanced or constant. But if I know $U_f$ I already know the answer to this question.

I am a little confused...


If you see the operator only from the unitary matrix point of view and you enumerate all inputs/outputs, which makes you visualize the matrix, indeed you somehow already know the answer.

However, imagine now $n$ is very large, say just $n>50$ or $n>60$, it becomes a bit difficult to store a $2^n * 2^n$ unitary matrix. But if you can compute the function, that is having a sequence of gates representing the operation, you can just apply it without having a knowledge of the unitary.

Let us give you an example just on n=3: $$ f(x) = x_0 \oplus x_1 x_2 $$

To apply $ U_f $, we just need a $CNOT$ and a Toffoli gate representing the different operations of $f$, and apply directly, without necessarily having a knowledge of the unitary to build it (just decomposing into "simple" operations). You can extend to examples where $n$ is very large.

  • $\begingroup$ Nice answer! Could you possibly comment on the case where $n=\omega$ (ie tranfinite/intinite dimensional)? $\endgroup$ – user820789 Nov 5 '18 at 16:34
  • 1
    $\begingroup$ Well the algorithm assumes $f(x)$ takes values for $ x \in \{0,1,...2^n-1 \} $, that is the input is represented by a binary string. $\endgroup$ – cnada Nov 5 '18 at 16:46
  • $\begingroup$ In this context, would it be more appropriate to use cardinal or ordinal arithmetic? $\endgroup$ – user820789 Nov 5 '18 at 16:51
  • 1
    $\begingroup$ I guess you got it in your terms @StarBucK. $\endgroup$ – cnada Nov 6 '18 at 10:52
  • 1
    $\begingroup$ @StarBucK You're welcome. Don't forget to validate one answer when you feel one is good enough. $\endgroup$ – cnada Nov 6 '18 at 14:10

I think there are probably two points to make here:

  1. The way that one implements quantum computation is not by simply looking at the unitary matrix and building something out of that, in just the same way that classical computation is not performed simply by first building the truth table and working off that (otherwise all classical computations would be exponential). Instead, as cnada says, the computation is itself built out of simple gates. The simplest is "do nothing" which is a perfectly good example of a constant algorithm. I don't need to see the unitary to build that!

  2. The context of an oracle is that you don't build it yourself, so you don't know the unitary. Somebody else gives it to you (or perhaps you'll have built it as the result of another computation), with certain promised properties, and it is your job to determine the relevant parameters. Of course, if you want to practically test whether that works, you'll build it all yourself. But then, you don't care about the efficiency saving during the test, because of course you know what you've built. Indeed, you need to know what you've built because otherwise your test cannot work; you don't know what to check the outcome against.

Incidentally, I think this question is closely related.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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