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 2


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

  • $\begingroup$ Thanks, it's been a long time since I used induction, I forgot it existed $\endgroup$
    – user82235
    Mar 9, 2014 at 9:14
  • $\begingroup$ Well, you better read my answer carefully again or do you want to misunderstand ? $\endgroup$
    – pressure
    Mar 9, 2014 at 11:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – Danu
    Mar 9, 2014 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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