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?

  • $\begingroup$ Possible duplicate of: physics.stackexchange.com/q/102670 $\endgroup$ – Jakob Mar 16 at 15:40
  • $\begingroup$ 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. $\endgroup$ – Emilio Pisanty Mar 17 at 11:27
  • $\begingroup$ A user points out via a flag that it's hard to distinguish this question from another similar question by you $\endgroup$ – rob Mar 18 at 1:45
  • $\begingroup$ It is advisable to leave the LaTex Code in the title to a minimum. The search function looks only for words, not in formulas. $\endgroup$ – DanielC Mar 18 at 12:46

You can use an argument by way of induction as has been linked in the comments; or you can see it intuitively:

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


Not the answer you're looking for? Browse other questions tagged or ask your own question.