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$?

  • $\begingroup$ 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. $\endgroup$ Commented Jan 27, 2015 at 11:40

1 Answer 1


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.

  • 1
    $\begingroup$ @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.) $\endgroup$ Commented Jan 27, 2015 at 22:43
  • $\begingroup$ 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)$ ? $\endgroup$
    – Zach Dean
    Commented Jan 28, 2015 at 10:17
  • $\begingroup$ @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? $\endgroup$ Commented Jan 28, 2015 at 11:00
  • $\begingroup$ 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? $\endgroup$
    – Zach Dean
    Commented Jan 28, 2015 at 13:37
  • $\begingroup$ @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.` $\endgroup$ Commented Jan 28, 2015 at 16:19

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.