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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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