# Why does the Hadamard act as $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{y\ \in\{0,1\}^n}(-1)^{x_1y_1+···+x_ny_n}|y\rangle$? [duplicate]

In quantum-information, we have been told that the Hadamard gate over $$n$$-qubits can be defined as:

$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}}\sum_{y\ \in\{0,1\}^n}(-1)^{x_1y_1+···+x_ny_n}|y\rangle \\= \mathbb C^2 \otimes ... \otimes \ \mathbb C^2 = \mathbb C^{2^n}, \text{ where }|x\rangle = |x_1,x_2,...,x_n\rangle$$

However, I do not have any intuition about how this is constructed from the single qubit Hadamard:

$$\frac{1}{\sqrt{2}}\begin{bmatrix}\begin{array}{rrrrrrrr} 1 & 1 \\ 1 & -1 \end{array}\end{bmatrix}.$$

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?

• Possible duplicate of: physics.stackexchange.com/q/102670 – Jakob Mar 16 at 15:40
• For full clarity, the first three votes to close were as off-topic, since this question falls outside the box laid out by the site's guidelines for homework and exercise questions as well as check-my-work questions, both of which you should read carefully. We intend our questions to be potentially useful to a broader set of users than just the one asking, and we prefer conceptual questions over those just asking for a specific computation. – Emilio Pisanty Mar 17 at 11:27
• A user points out via a flag that it's hard to distinguish this question from another similar question by you – rob Mar 18 at 1:45
• It is advisable to leave the LaTex Code in the title to a minimum. The search function looks only for words, not in formulas. – DanielC Mar 18 at 12:46

$$H^{\otimes n} | x \rangle= H^{\otimes n} | x_1, x_2,...,x_n \rangle$$ $$=\big(H|x_1 \rangle\big) \otimes \big(H|x_2 \rangle\big) \otimes...\otimes \big(H|x_n \rangle\big)$$ $$=\big(\frac{1}{\sqrt2}\big)^n \big(|0 \rangle+(-1)^{x_1}|1 \rangle\big)...\big(|0 \rangle+(-1)^{x_n}|1 \rangle\big)$$ $$=\frac{1}{\sqrt{2^n}} \prod_i|0 \rangle+(-1)^{x_i}|1 \rangle$$ $$=\frac{1}{\sqrt{2^n}} \sum_{y \in\{0,1\}^n}f(y,x) |y \rangle$$
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 $$H^n$$, 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 $$y_i=1$$ then the term is a $$|1 \rangle$$ and if $$x_i=1$$ then the coefficient of that $$|1 \rangle$$ is negative. So iff $$x_iy_i=1$$ then we have a negative factor contributing to the $$|y \rangle$$, 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: $$=\frac{1}{\sqrt{2^n}} \sum_{y \in\{0,1\}^n} (-1)^{\sum_i^n x_iy_i} |y \rangle$$ $$=\frac{1}{\sqrt{2^n}} \sum_{y \in\{0,1\}^n} (-1)^{x \cdot y} |y \rangle$$