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

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