How to apply a Hadamard gate?

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>)$?

-
You can apply the Hadamard transform $H^{\otimes 3}$ to all three qubits, as Lubos shows how to do in his answer. This is equivalent to applying a Hadamard gate to each of the three qubits. You can also apply a Hadamard gate to any one of the three qubits. You really shouldn't say you're applying a Hadamard gate to all three qubits. – Peter Shor Mar 3 '13 at 18:29
Do you mean how does one apply $H$ to an individual (e.g. "the first") qubit? – raxacoricofallapatorius Mar 12 '13 at 1:02

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.

-

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.

-