# Tensor product of Hadamard operators

The Hadamard Operator on one qubit is:

\begin{align*} H = \tfrac{1}{\sqrt{2}}\left[\,\left(\color{darkgreen}{|0\rangle + |1\rangle}\right)\color{darkblue}{\langle 0|}+\left(\color{darkgreen}{|0\rangle - |1\rangle}\right)\color{darkblue}{\langle 1|}\,\right] \end{align*}

Show that: \begin{align*} H^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{x,y}(-1)^{x \cdot y}\,\left|x\rangle \langle y\right| \end{align*}

I can evaluate things like $H \otimes H$ in practice, but I don't know how to get a general formula for $H^{\otimes n}$. Are there any tricks I could use?

## 2 Answers

The Keyword here is mathematical induction: Suppose that the formula holds for some $n$ and show that therefore it holds for $n+1$. If you additionally show that it holds for $n=2$, you have shown the general formula for arbitrary $n$.

• Thanks, it's been a long time since I used induction, I forgot it existed – user82235 Mar 9 '14 at 9:14
• Well, you better read my answer carefully again or do you want to misunderstand ? – pressure Mar 9 '14 at 11:15
• @pressure I apologize, somehow I must've misread the answer, because reviewing the revision history shows that the $n \rightarrow n+1$ step was actually in there all along. I dont understand what happened that caused me to misread it. – Danu Mar 9 '14 at 21:16

This can be shown directly. The definition you posted can be seen as the single-qubit version of your target, $$H=\frac{1}{\sqrt{2}}\sum_{x_1,y_1}(-1)^{x_1 y_1}| x_1 \rangle\langle y_1 |.$$ The $n$-qubit case is then \begin{align} H^{\otimes n} &=\frac{1}{\sqrt{2^n}}\left(\sum_{x_1,y_1}(-1)^{x_1 y_1}| x_1 \rangle\langle y_1 |\right) \otimes\cdots\otimes \left(\sum_{x_n,y_n}(-1)^{x_n y_n}| x_n \rangle\langle y_n |\right) \\& =\frac{1}{\sqrt{2^n}}\sum_{x_1,\ldots,x_n \\ y_1,\ldots,y_n}(-1)^{x_1 y_1}\cdots(-1)^{x_n y_n}| x_1 \rangle \otimes\cdots\otimes | x_n \rangle\langle y_1 | \otimes\cdots\otimes \langle y_n | \end{align} by expanding the sum. The only difference between this and your goal, $$H^{\times n}=\frac{1}{\sqrt{2^n}}\sum_{x,y}(-1)^{x \cdot y}| x \rangle\langle y |,$$ is notation.