# Deutsch's Algorithm. Unitary Transform $U_f$

I'm studying Deutsch's algorithm and I keep coming across the phrase along the lines of "There is a unitary transform (a sequence of quantum gates) $U_f$ that transforms the state $|x\rangle |y\rangle \rightarrow |x\rangle |y \oplus f(x)\rangle$".

I was trying to figure out how this $U_f$ would be implemented as a sequence of quantum gates.

I originally thought that there would be some sort of transform that takes $|x\rangle \rightarrow |f(x)\rangle$ and then apply the CNOT transformation to obtain the result. However, I believe this way of thinking is incorrect and I wouldn't obtain the state desired.

So how is the transform $U_f$ realised or does it depend upon the function $f$?

• Quantum circuits have to be reversible. If you would map $\vert x\rangle \rightarrow \vert f(x)\rangle$, this might not be reversible (e.g. for the constant function). Thus, the way to deal with it is to use an ancilla $\vert y \rangle$ in which the result is stored. Commented Jan 27, 2015 at 11:40

Your $U_f$ must depend on $f$. Let's consider the two trivial examples:

1. $f$ is the zero-function. In this case, $U_f$ is just the identity.

2. $f$ is the one-function ($x\mapsto 1$), then $|x\rangle|y\rangle \mapsto |x\rangle|y\oplus 1\rangle$, then $U_f$ is a NOT-gate on the second qubit.

Just a note: The whole idea of the Deutsch-Josza algorithm is that you don't need to worry about how to implement $U_f$ - it is given.

• @ZachDean Note that how to realize such a function is shown in C. H. Bennett, IBM Journal of Research and Development 17, 525 (1973). (This is for classical circuits, but every classical reversible circuit equals a unitary.) Commented Jan 27, 2015 at 22:43
• With the circuit diagram for the transform $U_f$ we have the two inputs $x$ and $y$ and the two outputs $x$ and $y \oplus f(x)$. However, can we not obtain an entangled state as the output, i.e that it can't be written as the tensor product of the two outputs from $U_f$? For example $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle +|1\rangle$) and $|y\rangle = |0\rangle$ then the combined input state to $U_f$ is $|input\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ Then if $f(0) = 1$ and $f(1)=0$ the output will be $|ouptut\rangle = \frac{1}{\sqrt{2}}(|01\rangle + |10\rangle)$ ? Commented Jan 28, 2015 at 10:17
• @ZachDean Why should your input be $\lvert00\rangle+\lvert11\rangle$? It is $\lvert00\rangle+\lvert10\rangle$. The output is correct though, and this is an entangled state. Could you clarify your question? Commented Jan 28, 2015 at 11:00
• Sorry I see my error. However, if it was possible to obtain an output as an entangled state from $U_f$ then I feel the circuit diagram of $U_f$ is misleading. This is because it shows that the output is $|x\rangle$ and $|y\oplus \rangle$, my point being it may not always be possible to seperate the combined state into these two outputs? Does this mean that $U_f$ never produces an entangled output? Commented Jan 28, 2015 at 13:37
• @ZachDean Didn't you just yourself give an example above for a function which can give an entangled output for a classical function? Note that the notation only says that for classical inputs the output is unentangled. P.S.: If you want me to be notified about your comments you should add @NorbertSchuch in them.` Commented Jan 28, 2015 at 16:19