Why do multi-bit hadamards expands to what they do?

Question

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

Answer 1

Your first formula is not correct. The correct formula for Hadamard gates for the arbitrary $|x\rangle$ from the calculational basis is (it can be proved by induction): $$H^{\otimes n}|x\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}{(-1)^{x\cdot y}}|y\rangle$$

where $x\cdot y=x_0y_0\oplus x_1y_1\oplus x_2y_2\oplus ...\oplus x_ny_n$

In case $|x\rangle = |0\rangle$ then $$x\cdot y =0\cdot y = 0$$ and $$H^{\otimes n}|x\rangle=H^{\otimes n}|0\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}{(-1)^{0}}|y\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}|y\rangle$$ in this case $$H^{\otimes n}H^{\otimes n}|0\rangle=H^{\otimes n}(\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}|y\rangle)=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}H^{\otimes n}|y\rangle=$$ $$=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}(\frac{1}{\sqrt{2^n}} \sum_{z=0}^{2n-1}{(-1)^{z\cdot y}}|z\rangle)=\frac{1}{2^n} \sum_{y=0}^{2n-1}\sum_{z=0}^{2n-1}{(-1)^{z\cdot y}}|z\rangle=\frac{1}{2^n} \sum_{z=0}^{2n-1}\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}}|z\rangle=\frac{1}{2^n} \sum_{z=0}^{2n-1}|z\rangle(\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}})=\frac{1}{2^n} |0\rangle(\sum_{y=0}^{2n-1}{(-1)^{0\cdot y}})+\frac{1}{2^n} \sum_{z=1}^{2n-1}|z\rangle(\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}})=\frac{1}{2^n} |0\rangle(2^n)+\frac{1}{2^n} \sum_{z=1}^{2n-1}|z\rangle(\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}})=|0\rangle+\frac{1}{2^n} \sum_{z=1}^{2n-1}|z\rangle\cdot0=|0\rangle$$

In the same way it can be proved that: $$H^{\otimes n}H^{\otimes n}|x\rangle=|x\rangle$$

Answer 2

The $(-1)^{x\cdot y}$ terms come from the matrix elements of $H^{\otimes n}$.

To see this, start from considering the matrix elements of $H$. You can check that they can be written as $H_{ij}=(-1)^{ij}$ where $i,j\in\{0,1\}$.

The matrix elements of $H^{\otimes n}$ are indexed by tuples of $n$ binary numbers, that is, writing $I\equiv (i_1,...,i_n), J\equiv(j_1,...,j_n)$, we have $$(H^{\otimes n})_{IJ} = \prod_{k=1}^n H_{i_k ,j_k} = \prod_{k=1}^n (-1)^{i_k j_k} = (-1)^{\sum_{k=1}^n i_k j_k} \simeq (-1)^{\boldsymbol i\cdot\boldsymbol j},$$ where in the last step we used the same notation as in the OP.

Note that I'm ignoring the normalisation factors here, so just add back the $1/2^{n/2}$ factors around as needed.