# Analysis of the second Hadamard in the Detusch-Jozsa Algorithm

Consider the Deutsch-Jozsa, algorithm, which first initializes the state $$|0 \rangle^{\otimes n} | 1 \rangle$$, creates a superposition using the the Hadamard gate and the $$U_f$$ to get into the state: $$\sum_x (-1)^{f(x)} |x \rangle (|0 \rangle - | 1 \rangle).$$

So far I can follow. What I don't understand is the step where we we apply the Hadamard gate to the first $$n$$ qubits, which gives (ignoring the last qubit) $$\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left [ \sum_{y=0}^{2^n-1} (-1)^{x \cdot y} |y\rangle \right ].$$

How can I prove that applying the Hadamard to the $$n$$ qubits in the state $$\sum_x (-1)^{f(x)} | x \rangle$$ gives the above sum?

If you look at the formula you want to prove term-by-term, you'll notice that the sum and the $$(-1)^f(x)$$ part is the same in both formulas; you just need to show that
$$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \left( \sum_{y=0}^{2^n-1} (-1)^{x \cdot y} |y\rangle \right )$$
You can either show this strictly by induction (similar to this question but accounting for the fact that $$|x\rangle$$ can have both $$|0\rangle$$ and $$|1\rangle$$ bits which contribute different signs to the term).
Alternatively, you can just look at it: $$|x\rangle$$ is a sequence of $$|0\rangle$$ and $$|1\rangle$$ states, so applying a Hadamard gate to each of them will produce all possible sequences of $$|0\rangle$$s and $$|1\rangle$$s to serve as $$|y\rangle$$s. The sign before each $$|y\rangle$$ term is defined as follows: minus signs only appear when you apply Hadamard to a $$|1\rangle$$ bit of $$|x\rangle$$ and you consider a term $$|y\rangle$$ which has a $$|1\rangle$$ bit in the corresponding position. The coefficient $$(-1)^{x \cdot y}$$ accumulates from counting such positions for the given $$|x\rangle$$ and $$|y\rangle$$ and multiplying the signs.