Prove that the product of two n qubits Hadamard gates is identity

[Haorong Wu]

Homework Statement:

Prove $H^{\otimes n} \cdot H^{\otimes n} = I$

Relevant Equations:

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

where $x \text { and } y \text { are from } 00 \dots 00 \text { to } 11 \dots 11$, and $x \cdot y = x_1 y_1 + x_2 y_2 + \cdots + x_n y_n$

From the properties of tensor product, $H^{\otimes n} \cdot H^{\otimes n} =\left ( H_1 \cdot H_1 \right ) \otimes \left ( H_2 \cdot H_2 \right ) \otimes \cdots \otimes \left ( H_n \cdot H_n \right ) =I \otimes I \otimes \cdots \otimes I =I$ where $H_i$ acts on the $i^{th}$ qubit.

But I want to try another way from the definition of $H^{\otimes n}$:

$H^{\otimes n} \cdot H^{\otimes n} \\ =\left [ \frac 1 {\sqrt {2^n}} \sum_{x,y} {\left ( -1 \right )} ^{x \cdot y} \left | x \right > \left < y \right | \right ] \left [ \frac 1 {\sqrt {2^n}} \sum_{i,j} {\left ( -1 \right )} ^{i \cdot j} \left | i \right > \left < j \right |\right ] \\ = \frac 1 {2^n} \sum_x \sum_y \sum _j {\left ( -1 \right )} ^{x \cdot y} {\left ( -1 \right )} ^{y \cdot j} \left | x \right > \left < j \right | \\ = \frac 1 {2^n} \sum_x \sum_j \left ( \sum _y {\left ( -1 \right )} ^{x \cdot y} {\left ( -1 \right )} ^{y \cdot j} \right ) \left | x \right > \left < j \right |$

I'm stuck because I have no idea how to properly calculate $\sum _y { \left ( -1 \right )} ^{x \cdot y} {\left ( -1 \right )} ^{y \cdot j}$. The answer should be $0$ if $x \neq j$, and $1$ otherwise.

Any advice? Thanks!

 

[jedishrfu]

I don't know the best solution here but perhaps this will help.

Try bringing the y power inside to give $(-1^y)$ and play with combinations of x,j, and y being even or odd to see if you can find a pattern in the series.

 

[Haorong Wu]

I don't know the best solution here but perhaps this will help.

Try bringing the y power inside to give $(-1^y)$ and play with combinations of x,j, and y being even or odd to see if you can find a pattern in the series.

Thanks, jedishrfu. I'll try it.

 

[jedishrfu]

It might not be the right approach but until someone posts otherwise here its something that I'd try.

I noticed that when y is even $(-1^y)$ evaluates to 1 and when odd a -1 so now you can look at how x+j behaves.

 

[tnich]

I think you could prove this by induction. $HH=I$ is trivial. Then you just need to write
$H^{\oplus n+1}$ in terms of $H^{\oplus n}$ and do the matrix mulitiplication.

 

[Haorong Wu]

I think you could prove this by induction. $HH=I$ is trivial. Then you just need to write
$H^{\oplus n+1}$ in terms of $H^{\oplus n}$ and do the matrix mulitiplication.

Brilliant! Thanks, tnich!