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.

Some common quantum gates

Identity: $\ket{x} \mapsto \ket{x}$

$I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

NOT (Pauli X): $\ket{x} \mapsto \ket{1 \oplus x}$

$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$

Pauli Y:

$Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$

Pauli Z:

$Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$

Hadamard:

$H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

CNOT: $\ket{x} \ket{y} \mapsto \ket{x} \ket{x \oplus y}$

$C = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{pmatrix}$

Phase shift:

$R_\theta = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\theta} \end{pmatrix}$

(To be continued)