# How to construct the unitary representation of the function $f(x, y, z) = (x \oplus y, y \oplus z)$?

Consider the function $$f:\{0, 1\}^3\to\{0, 1\}^2$$ with $$f(x, y, z) = (x \oplus y, y \oplus z)$$. How would you construct its standard unitary representation?

• Unitary transformations are reversible, the function is not. – kludg Dec 2 '19 at 18:24
• @kludg Well, ancillary qubits always come to the rescue. – Sanchayan Dutta Dec 3 '19 at 9:23

There’s not exactly a standard way of doing it. The first thing you have to do is make the transformation unitary. The way that’s guaranteed to work is to introduce 2 extra qubits. However that’s not necessary in this case. Instead, the circuit is very simple: controlled not controlled from y targeting z, followed by controlled not controlled from x and targeting y.

This is for the function $$g : \{ 0,1 \}^3 \to \{0,1\}^3$$ $$g(x,y,z)=(x,x\oplus y , y \oplus z)$$

• by "there isn't a standard way to do this" do you mean that there isn't a canonical choice of "unitarization" of the function? With this I agree. But I would say that there is a standard procedure to solve this kind of problem. If you can look at the truth table of the function, the least number of ancillas you need to make it into a reversible gate is exactly equal to the (ceil of) the $\log_2$ of the maximum number of equal outputs assigned to the same input, that is $\lceil \log_2 \max_y |f^{-1}(y)|\rceil$ – glS Dec 3 '19 at 11:24

A good way to start is to have a look at the truth table of the function:

$$\begin{array}{ccccc} x & y & z & \text{out1} & \text{out2} \\\hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ \end{array}$$

An interesting feature you might notice from this is that each output $$(o_1,o_2)$$ occurs exactly twice. This tells you that a single ancilla is enough to make this into a unitary mapping.

To build this mapping, you simply need to add a third output to each input $$(x,y,z)$$, taking care to assign different outcomes whenever two triples $$(x,y,z)$$ and $$(x',y',z')$$ are assigned the same value by $$f$$. Clearly, there are multiple ways to do this (more precisely, there are $$2^4$$ ways to do it). Once this assignment is done, the unitary transformation you are looking for is the corresponding permutation matrix.

An example would be the following:

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix}.$$