Deutsch-Jozsa Algorithm

Denote $\Z_2$ the field with 2 elements. A function $f: \Z_2^n \rightarrow \Z_2$ is said to be balanced if $|f^{-1}(0)| = |f^{-1}(1)|$.

Problem: Suppose $f: \Z_2^n \rightarrow \Z_2$ is either constant or balanced. Determine whether $f$ is constant or balanced.
Given: A quantum oracle for $f$, represented by $U_f: \ket{\mathbf{x}}\ket{y} \mapsto \ket{\mathbf{x}}\ket{y \oplus f(\mathbf{x})}$.

Deutsch-Jozsa algorithm:
1. Prepare an (n + 1)-qubit initial state \[ \ket{\psi_1} = \ket{\mathbf{0}}\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right). \]
2. Apply $\otimes_{k = 1}^n H$ to the first n-qubit. Get \[ \ket{\psi_2} = \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \ket{\mathbf{k}} \left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right). \]
3. Apply $U_f$ to obtain \[ \ket{\psi_3} = \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} (-1)^{f(\mathbf{k})}\ket{\mathbf{k}} \left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right). \]
4. Apply again $\otimes_{k = 1}^n H$ to the first n-qubit. Get \[ \ket{\psi_4} = \frac{1}{2^n}\sum_{k = 0}^{2^n - 1} (-1)^{f(\mathbf{k})}\sum_{s = 0}^{2^n - 1} (-1)^{\mathbf{k} \cdot \mathbf{s}}\ket{s}\left( \frac{\ket{0} - \ket{1}}{\sqrt{2}} \right). \]
5. If $f$ is constant, then $\ket{\psi_4} = \ket{\mathbf{0}}\frac{\ket{0} - \ket{1}}{\sqrt{2}}$ by $\sum_{s = 0}^{2^n - 1} (-1)^{\mathbf{k} \cdot \mathbf{s}} = 0$ if $k \neq 0$ and $2^n$ if $k = 0$, so on measuring first n-qubit we get $\ket{\mathbf{0}}$ with probability one. If $f$ is balanced, then write $\ket{\psi_4} = \ket{\psi}\frac{\ket{0} - \ket{1}}{\sqrt{2}}$, we have \[ \braket{\mathbf{0}}{\psi} =  \frac{1}{2^n}\sum_{k = 0}^{2^n - 1} (-1)^{f(\mathbf{k})}\sum_{s = 0}^{2^n - 1} (-1)^{\mathbf{k} \cdot \mathbf{s}} \braket{\mathbf{0}}{\mathbf{s}} = \sum_{k = 0}^{2^n - 1} (-1)^{f(\mathbf{k})} = 0 \] and the probability of getting $\ket{\mathbf{0}}$ on measuring first n-qubit is zero. Therefore, we measure the first n-qubit. If the result is $\ket{\mathbf{0}}$, then $f$ is constant, otherwise $f$ is balanced.