Why isn't output of Deutsch–Jozsa Algorithm simply $|0\rangle$?

If I look at the circuit diagram of the Deutsch–Jozsa Algorithm: Now given the fact that Hadamard matrix or gate is its own inverse (see here), shouldn't the output (top wire) simply give back $$|0\rangle$$?

It may naively seem that gates like $$U_f$$ whose action is defined as

$$U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle$$

have no effect on the first register holding the state $$|x\rangle$$. This naive perception originates in our classical intuition. We see that the operation does not change the contents of the first register and in the classical world this is equivalent to having been unaffected by the operation. However, in quantum mechanics interactions can have other more subtle effects beyond changing register values. Specifically, they can introduce entanglement.

As a consequence, one cannot move the second Hadamard on the first register through $$U_f$$ to cancel it with the first Hadamard (or vice versa) as that would change the entanglement produced by $$U_f$$ and therefore would perform an inequivalent operation. Moreover, entanglement affects the interference patterns in a way that can have measurable effects on the output distribution of each register.

It is instructive to see how things play out in a concrete case. We will use the CNOT gate

$$CNOT|x\rangle|y\rangle = |x\rangle|y \oplus x\rangle \tag1$$

which is a simple variant of $$U_f$$. For simplicity, consider the action of a Hadamard on the first qubit followed by a CNOT followed by another Hadamard on the first qubit. This is simpler than Deutsch-Jozsa algorithm, but serves to demonstrate how entanglement may prevent the first register from reading $$|0\rangle$$ with certainty. We have

\begin{align} (H \otimes I) \circ CNOT \circ (H \otimes I) |0\rangle |0\rangle &= \frac{1}{\sqrt{2}}(H \otimes I) \circ CNOT (|0\rangle + |1\rangle)|0\rangle \\ &= \frac{1}{\sqrt{2}}(H \otimes I) (|0\rangle|0\rangle + |1\rangle|1\rangle) \\ &= \frac{1}{2} \left[|0\rangle + |1\rangle)|0\rangle + (|0\rangle - |1\rangle)|1\rangle\right] \\ &= \frac{1}{2} \left[|0\rangle|0\rangle + |1\rangle|0\rangle + |0\rangle|1\rangle - |1\rangle|1\rangle\right] \\ &= \frac{1}{2} \left[|0\rangle(|0\rangle + |1\rangle) + |1\rangle\color{red}{\underline{(|0\rangle - |1\rangle)}}\right] \\ \end{align}

where we collected the terms that correspond to the first qubit in the $$|0\rangle$$ and $$|1\rangle$$ states. Compare the calculation to what happens in the absence of the CNOT gate

\begin{align} (H \otimes I) \circ (H \otimes I) |0\rangle |0\rangle &= \frac{1}{\sqrt{2}}(H \otimes I) (|0\rangle + |1\rangle)|0\rangle \\ &= \frac{1}{2} \left[|0\rangle + |1\rangle)|0\rangle + (|0\rangle - |1\rangle)|0\rangle\right] \\ &= \frac{1}{2} \left[|0\rangle|0\rangle + |1\rangle|0\rangle + |0\rangle|0\rangle - |1\rangle|0\rangle\right] \\ &= \frac{1}{2} \left[|0\rangle(|0\rangle + |0\rangle) + |1\rangle\color{red}{\underline{(|0\rangle - |0\rangle)}}\right] \\ \end{align}

where as before we collected the terms corresponding to the first qubit in the $$|0\rangle$$ and $$|1\rangle$$ states. In the absence of CNOT, destructive interference zeroes out the amplitude of the $$|1\rangle$$ state (see the last underlined expression). However, in the presence of CNOT interference is prevented because the amplitudes reside on different kets due to entanglement introduced by the CNOT gate (see the earlier underlined expression).

Therefore, in the presence of CNOT, it is possible for the first register to read $$|1\rangle$$ even though naive reading of $$(1)$$ might suggest this should not happen.

Note that gates such as

$$U_c|x\rangle|y\rangle = |x\rangle|y\oplus f(c)\rangle$$

where the change to the second register's value is independent of the contents of the first register do not generate entanglement. In this case it is possible to write the action of the gate as $$U_c = I \otimes V$$ for a unitary $$V$$ and so the two Hadamards on the first register would cancel.

This is because of what known as Phase kickback. The phase of the bottom qubit can kick back and create a relative phase change on the top qubit. This is a very useful and often use trick in quantum computing. In fact, it is fundamental to the Quantum Phase Estimation algorithm.

• It seems like OP is asking why the 2 H gates in the first qubit do not cancel out. Phase kickback will indeed add a phase to the first qubit, but even if there was only one qubit, such that it went through H-X-H, the 2 H gates still don't "cancel out".
– a3y3
Dec 24 '20 at 16:34
• @a3y3 Yes. Upon answering the question I already saw that you already mentioned that so I thought to add a little more... and since phase kickback is such an important concept I decided to add it to the answer. Also people often question/confuse why would the controlled state change since it is just acting as a controlled-qubit and two Hadamard should cancel out. Dec 24 '20 at 17:09

Not really. You can't cancel the H gates on the first qubit because the order of gates matters. Similiar to matrix multiplication, ABC is not equal to ACB.

Just to add that the Oracle in the algorithm causes entanglement among first $$n$$ qubits and the last one. As you can see, the last qubit is in state $$f(x) \oplus y$$.This means that it is influenced by values of first $$n$$ qubits. As a result these qubits are also influenced by the last qubit. So, despite the double application of Hadamard, also first $$n$$ qubits contains information about the last qubit.

This answer is a little supplementation of @Martin Vesely.

It has been proven that "it is not possible to build a fixed, general quantum computer which can be programmed to perform an arbitrary quantum computation" by this paper.

To be more specific, suppose $$|d\rangle$$ is a data register $$|P\rangle$$ is a program(control) register, and denote the quantum program, which is a unitary operation act on both $$|d\rangle$$ and $$|P\rangle$$, by $$\hat G$$, there is not general guarantee that $$\hat G(|d\rangle\otimes|P\rangle)=(\hat U|d\rangle)\otimes|P\rangle$$ is possible, where $$\hat U$$ acts solely on $$|d\rangle$$.

If the $$U_f$$ is your question is such a quantum program $$\hat G$$(the upper qubit is the program register in your case), then the repeated implementation of Hadamard gate can cancel each other at last, but apparently, this is not the case.