Sunday, 8 September 2013

Consider the action of the Hadamard gate $H$ when acting on the basis states $\left|0\right>$ and $\left|1\right>$, and observe that this can be expressed as
$\begin{array}{r l} H\left|x\right> &= \frac{1}{\sqrt{2}}\big(\left|0\right>+(-1)^{x}\left|1\right>\big) \\ & =\frac{1}{\sqrt{2}}\displaystyle\sum\limits_{y\in\{0,1\}}(-1)^{x\cdot y}\left|y\right>. \end{array}$
Denote some bitstring $\mathbf{x}\in\{0,1\}^n$ as $\mathbf{x}=x_1x_2\dots x_n$, where each $x_i\in\{0,1\}$, and define the  following operation on bitsrings
$\mathbf{x}\cdot \mathbf{y}=(x_1y_1+x_2y_2+\dots +x_ny_n)mod2.$
The tensor product of Hadamard gate $H$ with itself $n$ times creates a gate similar to $H$, denoted by $H^{\otimes n}$, which operates on $n$ qubits. Its action is the same as applying the single qubit Hadamard transform $H$ to each of the $n$ qubits of the register. This gate sends the $n$ qubit register $\left|\mathbf{x}\right>=\left|x_1x_2\dots x_3\right>=\left|x_1\right>\left|x_2\right>\dots\left|x_n\right>$ to the state
$\begin{array}{r l} H^{\otimes n}\left|\mathbf{x}\right>&=H^{\otimes n}\left|x_1x_2\dots x_3\right> \\ & =H\left|x_1\right>H\left|x_2\right>\dots H\left|x_n\right>\\ & = \big(\frac{\left|0\right>+(-1)^{x_1}\left|1\right>}{\sqrt{2}}\big)\big(\frac{\left|0\right>+(-1)^{x_2}\left|1\right>}{\sqrt{2}} \big)\dots \big(\frac{\left|0\right>+(-1)^{x_n}\left|1\right>}{\sqrt{2}}\big) \\ & = \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{y_1y_2\dots y_n\in\{0,1\}^n}(-1)^{x_1y_1+x_2y_2+\dots +x_ny_n}\left|y_1\right>\left|y_2\right>\dots\left|y_n\right> \\ & = \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot \mathbf{y}}\left|\mathbf{y}\right>. \end{array}$
In the case where $\left|\mathbf{0}\right>=\left|00\dots 0\right>=\left|0\right>\left|0\right>\dots\left|0\right>,$
$H^{\otimes n}\left|\mathbf{0}\right>= \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}\left|\mathbf{y}\right>,$
since $(-1)^{\mathbf{x}\cdot \mathbf{0}}=1$, which is an equally weighted superposition of all bases states in the Hilbert space of dimension $2^n$.