# Understanding Deutsch Algorithm

From the image below, if we focus on the first qubit, we know after Hadamard (state 1) $$|0\rangle$$ will become $$|+\rangle$$ and the second qubit $$|1\rangle$$ will become $$|-\rangle$$.

What exactly would the result be after $$U_f$$? I understand that $$U_f$$ performs a CNOT gate on the qubits. But how is this result shown? By this I mean the image below is it (the equation for state 2), $$|0\rangle$$, $$|1\rangle$$, $$|+\rangle$$ or $$|-\rangle$$ and why is it that specific one? For instance, I presume state 2 would be $$|-\rangle$$? is it simply the process that if it was previously $$|+\rangle$$ then it just flips after going through CNOT gate to $$|-\rangle$$? In which state 3 then results in it being $$|1\rangle$$ ?
state 2:

By states I refer to the bottom numbered symbols within this image below.

The $$U_f$$ is not necessarily a controlled-not (although that is one possible example). Instead, what $$U_f$$ does is, for any 2-qubit input in a basis state $$|xy\rangle$$, if evaluates $$U_f|xy\rangle=|x\rangle|y\oplus f(x)\rangle.$$ The key trick here, of course, is that we're not supplying basis states, but superpositions. In particular, the second qubit is in the $$|-\rangle$$ state. Let's see the result of that: $$U_f|x\rangle|-\rangle=|x\rangle(|0\oplus f(x)\rangle-|1\oplus f(x)\rangle.$$ $$f(x)$$ could either be 0 or 1, in which case the two outputs couple be either \begin{align*} f(x)=0:&|0\oplus 0\rangle-|1\oplus 0\rangle=|-\rangle \\ f(x)=1:&|0\oplus 1\rangle-|1\oplus 1\rangle=-|-\rangle \\ \end{align*} This can be summarised as $$U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle.$$ Thus, your output at $$|\psi_2\rangle$$ is $$((-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle)|-\rangle/\sqrt{2}$$ Now you can easily apply the Hadamard to the first qubit, and see that the answer depends on the value $$(-1)^{f(0)+f(1)}$$.