# Encoding boolean function in a quantum circuit

Let $$U_f$$ be the quantum gate such that $$| x \rangle | y \rangle \mapsto | x \rangle |y\oplus f(x) \rangle$$, where $$x$$ is some bit string of size $$n$$, $$|y\rangle$$ is a qubit, and is $$f$$ is some boolean function. It is easy to show that if $$| y \rangle = | - \rangle$$ then the output is $$(-1)^{f(x )} |x \rangle | - \rangle$$. That is, the effect of $$f(x)$$ is moved from the last qubit to the phase of $$| x \rangle | - \rangle$$.

How can we do the opposite? That is, if we have some quantum gate such that $$| x \rangle \mapsto (-1)^{f(x)} | x \rangle$$. How can we move the effect of $$f(x)$$ from the phase of $$| x \rangle$$ to some other (extra) qubit $$| y \oplus f(x) \rangle$$?

I've tried entangling $$(-1)^{f(x)} |x \rangle$$ with $$| - \rangle$$ but I'm sort of stuck.

• Do you have access to a controlled version of the phase oracle? Commented Feb 11 at 17:21
• @TristanNemoz: I don't think so Commented Feb 11 at 18:14

It depends on how you have implemented the map that takes $$|x\rangle$$ to $$(-1)^{f(x)}|x\rangle$$. If you simply have a single qubit gate like that, it will be impossible to get out $$|y \oplus f(x)\rangle$$ because the $$(-1)^{f(x)}$$ is a global phase. Instead, let's assume your implementation has a control qubit (which I will draw as the second qubit and label $$|y\rangle$$. So, it adds the phase only if the second bit is inputted to be 1 and if the second bit is 0, it acts like identity. Then, your circuit can be interpreted as $$U_f$$ but with some Hadamard's around it.
Now, to get back to a function that puts $$|y \oplus f(x)\rangle$$ on the second qubit, we may use that the Hadamard is self inverse and obtain the following circuit.