How to apply a Hadamard gate?

Question

How to apply a Hadamard gate to 3 qubits? by example how to apply $H$ to $(1/\sqrt{2})(\left|000\right> + \left|111\right>)$?

Answer 1

By its definition, the Hadamard transform is given by the matrix whose entries are $$ (H_n)_{ij} = 2^{-n/2} (-1)^{i\cdot j} $$ where $i\cdot j$ is the bitwise dot product of the binary representations i.e. the number of times $1,1$ appears on the same places (digits) both in $i$ and $j$. For the case of three qubits, the matrix is $$ H_3 = \frac{1}{2^{\frac{3}{2}}} \cdot \begin{pmatrix}\begin{array}{rrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1\\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1\\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1\\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1\\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \end{array}\end{pmatrix}$$ You may multiply this matrix by your vector which is the column $$\frac{1}{\sqrt{2}} (1,0,0,0,0,0,0,1)^T $$ and you will get $$ \frac{1}{2} (1,0,0,1,0,1,1,0)^T $$ I only needed to look at the first and last columns of $H_3$. If there were two entries $1,1$ over there, the result had $(1/2^{3/2})\cdot (1/\sqrt{2})\times (1+1) = 1/2$ in the same row; if it were $1,-1$ or $-1,1$, the result had $0$ in the same row. Note that the resulting vector has unit norm as well, $4\times 1^2 / 2^2 = 1$, as guaranteed by the Hadamard matrix's being unitary.

The Hadamard transform is a sort of discrete Fourier transform. Note that you had $2$ equally represented entries in the original vector; it's not quite an accident that its Hadamard transform had $8/2=4$ nonzero entries (with the same absolute value). Here, $8$ is the total dimension of the Hilbert space and $2$ in the denominator was copied from the second sentence of this paragraph. This "inverse relationship" is analogous to the uncertainty relationship for $\Delta x$ and $\Delta p$: the more "localized" the original vector is, the more "delocalized" its Hadamard transform is.

Answer 2

To implement Lubos' formula in Mathematica, define the basic 1-qubit Hadamard gate as a 2 X 2 matrix variable. Then take KroneckerProduct[.,.] of the matrix with itself for (n-1)-times for an n-qubit Hadamard gate.