1
$\begingroup$

I might be asking something quite obvious but why is it stated that only one evaluation of $f$ is needed in the Deutsch-Jozsa algorithm?

If we have a quantum oracle for $f:\{0,1\}^n\rightarrow\{0,1\}$ and we apply the oracle to the $(n+1)$-qubit state, we get the quantum state $\frac{1}{\sqrt{2^{n+1}}}\sum_{n=0}^{2^n-1}|x\rangle (|f(x)\rangle-|1\oplus f(x)\rangle)$.

Why does the algorithm involve only a single evaluation of $f$? In order to apply the quantum oracle, doesn't the application of the quantum oracle involve full knowledge of the function $f$? Don't we have to calculate $f$ for $x=0,1,2,...,2^n-1$?

$\endgroup$
0