In quantum-information, we have been told that the Hadamard gate over n -qubits can be defined
as:
H⊗n|x⟩=1√2n∑y∈{0,1}n(−1)x1y1+⋯+xnyn|y⟩=C2⊗…⊗C2=C2n, where |x⟩=|x1,x2,…,xn⟩
However, I do not have any intuition about how this is constructed from the single qubit Hadamard:
1√2[111−1]
I am trying to figure out, and it thought of an induction over n, but do not know how to do it. Could anyone provide any help of proof?
You can use an argument by way of induction as has been linked in the comments; or you can see it intuitively:
H⊗n|x⟩=H⊗n|x1,x2,…,xn⟩=(H|x1⟩)⊗(H|x2⟩)⊗…⊗(H|xn⟩)=(1√2)n(|0⟩+(−1)x1|1⟩)…(|0⟩+(−1)xn|1⟩)=1√2n∏i|0⟩+(−1)xi|1⟩=1√2n∑y∈{0,1}nf(y,x)|y⟩
Now lets find f(x,y). Notice that in the product line, if we expand we only get one term for each basis element in the Hilbert Space Hn, and each term in the expanded sum has either a coefficient of +1 or -1 , based on the term itself and the x which is undergoing the Hadamard Transform. Also notice that every |0\rangle has a +1 coefficient, so only the |1\rangle terms can contribute to negativity. So for each term with an odd number of |1\rangle that have a negative coefficient, the expanded term will also have a negative coefficient.
Finally notice that if yi=1 then the term is a |1\rangle and if xi=1 then the coefficient of that |1\rangle is negative. So iff xiyi=1 then we have a negative factor contributing to the |y⟩, and of course if there is an odd number of those negative factors; the end result is a negative factor. This can be mathematically shown as:
=1√2n∑y∈{0,1}n(−1)∑nixiyi|y⟩=1√2n∑y∈{0,1}n(−1)x⋅y|y⟩