How is the Deutsch-Jozsa algorithm faster than classical for practical implementation?

Question

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

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

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 four possible $U_f$ associated to two constant possibilities ($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$ two 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 one 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...

Answer 1

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.

Answer 2

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.