Analysis of the second Hadamard in the Detusch-Jozsa Algorithm

Question

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?

Answer 1

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.