# 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!

## Answers and Replies

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

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

Homework Helper
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 and jedishrfu
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!