I'm a Computer Scientist undergrad student studying for an exam in Quantum computing. In all of the algorithms I have been studying (Deutsch–Jozsa, Simons, Shors, Grovers) I constantly see multi-qubit Hadamard gates being expended to the normalised sum of all the possible values like so:
$$\left|x\right>\xrightarrow{\mathbb H^{\otimes n}}\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\left|x\right>$$
That makes complete sense to me, however, it's when they perform another hadamard transformation on that state that I get a bit confused with the $(-1)^{x·y}$ that gets multiplied with each part of the superposition like so:
$$\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\left|x\right>\xrightarrow{\mathbb H^{\otimes n}}\sum_{x=0}^{2^n-1}\sum_{y=0}^{2^n-1}\left(-1\right)^{x.y}\left|y\right>$$ where
$$x.y = x_0y_0\oplus x_1y_1\oplus x_2y_2\oplus\ldots\oplus x_{n-1}y_{n-1}$$
I don't quite understand where this $(-1)^{x·y}$ has suddenly appeared from, or I don't have an intuition as to why it is required. My understanding was the performing one Hadamard after another kind of undoes the other?
Any intuition on this would be extremely helpful!
For a full reference I was triggered to ask here after seeing this happen in almost all the algorithms I mentioned above, but most recently here: Deutsch-Jozsa Algorithm