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?
How to construct the unitary representation of the function $f(x, y, z) = (x \oplus y, y \oplus z)$?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Unitary transformations are reversible, the function is not. $\endgroup$– kludgDec 2, 2019 at 18:24
-
$\begingroup$ @kludg Well, ancillary qubits always come to the rescue. $\endgroup$– Sanchayan DuttaDec 3, 2019 at 9:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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) $$
answered Dec 2, 2019 at 18:38
-
1$\begingroup$ 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$ $\endgroup$– glS ♦Dec 3, 2019 at 11:24
$\begingroup$
$\endgroup$
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.
