# 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)}$$.

• Ohh okay.. so state 2 would be |-> for qubit 2 and |+> for qubit 1 and state 3 would be in fact |1> for qubit 2 and |0> for qubit 1? So for the first qubit being in the |+⟩ state, the result will be Uf|x⟩|+⟩=|x⟩(|0⊕f(x)⟩+|1⊕f(x)⟩. where f(x) could either be in 0 or 1 again, in which case the two outputs could be either f(x)=0:|0⊕0⟩+|1⊕0⟩ =+ OR f(x)=1:|0⊕1⟩+|1⊕1⟩=+|+⟩ Commented Apr 14, 2021 at 14:18