Worked Problems in Physics

Nielsen and Chuang Exercise 2.33

Posted in Nielsen/Chuang by rpmuller on March 8, 2010

Exercise 2.33 The Hadamard operator on one qubit may be written as:

\displaystyle  H = \frac{1}{\sqrt{2}}\left[(\left<0\right|+\left<1\right|)\left<0\right|+(\left<0\right|-\left<1\right|)\left<1\right|\right]

Show explicitly that the Hadamard transform on n qubits, {H^{\otimes n}}, may be written as

\displaystyle  H^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{xy}(-1)^{x\cdot y}\left|x\right>\left<y\right|

Write out an explicit matrix representation for {H^{\otimes 2}}.

The matrix representation for {H^{\otimes 2}} is given by

\displaystyle  H^{\otimes 2}=\left[\begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\right].

We will prove that {H^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{xy}(-1)^{x\cdot y}\left|x\right>\left<y\right|} inductively. First, for {n=1},

\displaystyle  H^{\otimes 1} = \frac{1}{\sqrt{2}}\left[\left|0\right>\left<0\right|+\left|0\right>\left<1\right|+\left|1\right>\left<0\right|-\left|1\right>\left<1\right|\right]

which has the proper form. Next, given {H^{\otimes n}}, we can show that

\displaystyle  H\otimes H^{\otimes n} = \frac{1}{\sqrt{2^{n+1}}}\sum_{xy}(-1)^{x\cdot y} \left(\left|0x\right>\left<0y\right|+\left|1x\right>\left<0y\right|+\left|0x\right>\left<1y\right|-\left|1x\right>\left<1y\right|\right) =H^{\otimes n+1}

which completes the proof.

I cannot think of any way to prove this other than inductively. If anyone has a way, please leave a comment.