Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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$.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.