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

Question

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?

Answer 1

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

Answer 2

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

See also this other answer to a similar problem.