Derivation of the state after applying $U_f$ in the Deutsch–Jozsa algorithm

On page 35 in Nielsen and Chuang, it's said that for the following quantum circuit implementing the general Deutsch–Jozsa algorithm:

Next, the function $$f$$ is evaluated (by Bob) using $$U_f$$, giving $$\left|\psi_2\right\rangle=\sum_x\frac{(-1)^{f(x)}|x\rangle}{\sqrt{2}^n}\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]$$

I'm confused about where the $$(−1)^{f(x)}$$ come from.

• – glS
Sep 17, 2021 at 7:08

First of all, if we write down $$\left|\psi_1\right\rangle$$, we get: $$\left|\psi_1\right\rangle=\frac{1}{\sqrt{2}^n}\sum_x|x\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right].$$ Applying $$f$$ on this state gives us: $$\left|\psi_2\right\rangle=\frac{1}{\sqrt{2}^n}\sum_x|x\rangle\left[\frac{|f(x)\rangle-|1\oplus f(x)\rangle}{\sqrt{2}}\right].$$ Note that $$f(x)$$ is a bit. As such, $$f(x)\oplus 1$$ is actually $$f(x)$$ on which one applied a NOT gate. So, for a given $$x$$, if $$f(x)=0$$, then we can write: $$|f(x)\rangle-|1\oplus f(x)\rangle = |0\rangle-|1\rangle$$ while we can write, if $$f(x)=1$$: $$|f(x)\rangle-|1\oplus f(x)\rangle = |1\rangle-|0\rangle = -\left(|0\rangle-|1\rangle\right).$$ Thus, it is completely equivalent to write, in the general case: $$|f(x)\rangle-|1\oplus f(x)\rangle = (-1)^{f(x)}\left(|0\rangle-|1\rangle\right).$$ Indeed, in the case $$f(x)=0$$, the $$(-1)$$ will disappear, while in the case $$f(x)=1$$, it will stay, just like in the two previous equations. This means that we can rewrite the state as: $$\left|\psi_2\right\rangle=\frac{1}{\sqrt{2}^n}\sum_x|x\rangle(-1)^{f(x)}\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]$$ which is the state described in Nielsen and Chuang.