4
$\begingroup$

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?

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

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

$\endgroup$
  • 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 at 11:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.