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)

No-cloning Theorem

In a classical computer there is no problem to copy an arbitrary piece of data. However, in quantum computer this is not the case. This is the consequence of a straightforward observation in linear algebra, called the "No-cloning Theorem". In the formalism of quantum computation, we use a unit vector in a Hilbert space to represent the state of a quantum bit. Operations on quantum bits are represented by unitary operators on the Hilbert space. To represent a system with more than one quantum bit, we use tensor products. Here is the No-cloning Theorem in this formulation.


No-cloning Theorem. Let $\mathcal{H}$ be a vector space (over $\mathbb{R}$ or $\mathbb{C}$) of dimension larger than 1. There do not exist a linear operator $U$ on $\mathcal{H} \otimes \mathcal{H}$ and a nonzero vector $v_0 \in \mathcal{H}$ such that $U(x \otimes v_0) = x \otimes x$ for all $x \in \mathcal{H}$.
Proof: Suppose such a $U$ and $v_0$ exist. Choose a nonzero vector $v \in \mathcal{H}$ such that $v, v_0$ are linearly independent. Then $U(v_0 \otimes v_0) = v_0 \otimes v_0, U(v \otimes v_0) = v \otimes v$ and $U((v + v_0) \otimes v_0) = (v + v_0) \otimes (v + v_0) = v \otimes v + v_0 \otimes v + v \otimes v_0 + v_0 \otimes v_0$. But linearity of $U$ demands $U((v + v_0) \otimes v_0) = U(v \otimes v_0) + U(v_0 \otimes v_0) = v \otimes v + v_0 \otimes v_0$. This is a contradiction.