mjhjmtu

$newcommandqr[1]$ I gave myself the task of building an operator that implements the following function: $f(0) = 0$, $f(1) = 1$, $f(2) = 1$, $f(3) = 0$. I restricted myself to $x$ up to 2 bits. That is, $f$ tells the parity of its argument.

I read that in order to be reversible, a circuit $U_f$ could be defined to have the following effect: $U_fqrx_2 qr0_1 to qrx_2qr0 oplus f(x)_1$. After doing my calculations, I think the following matrix represents $U_f$

$$beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 1 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix otimes I_2$$

However, I'm really not sure. I once read that this definition isn't complete, that I should also define the behavior for the input $qrx_2qr1$. (I'm not too clear on that.)

So --- though confused ---, I went ahead and defined $$U_fqrx_2 qr1_1 to qrx_2qr1 oplus f(x)_1.$$ Doing my calculations again, I get the following matrix

$$beginbmatrix
0 & 1 & 1 & 0\
1 & 0 & 0 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix otimes I_2$$

Now I don't know which should be my matrix.

Since your desired operation is a non-injective function, you need a third qubit and a unitary acting on all three qubits. Using an operator on your two input qubits and tensoring this with $rm I_2$ on the third qubit is not going to work as you might as well forget about the third qubit completely if that were the case.

By the way, the two matrices you present aren't unitary ($rm U^daggerrm U=rm I_4$ with $^dagger$ the conjugate transpose does not hold), and tensoring a non-unitary matrix with $rm I_2$ won't make it unitary either.

So, let's start over: take three qubits, define the first two as your input registers and the third as your output register. Then, what you want your operation to do, is this:
$$rm U_f|000rangle=|000rangle\
rm U_f|010rangle=|011rangle\
rm U_f|100rangle=|101rangle\
rm U_f|110rangle=|110rangle$$
Note that to fully define $rm U_f$, we would have to determine a desired output for the four other possible (computational basis) input states, $|!*!*1rangle$. How we do this is entirely up to us! So we can just choose something convenient, such as this:
$$rm U_f|001rangle=|001rangle\
rm U_f|011rangle=|010rangle\
rm U_f|101rangle=|100rangle\
rm U_f|111rangle=|111rangle$$
This has the following matrix form:
$$rm U_f=beginbmatrix
1&0&0&0&0&0&0&0\
0&1&0&0&0&0&0&0\
0&0&0&1&0&0&0&0\
0&0&1&0&0&0&0&0\
0&0&0&0&0&1&0&0\
0&0&0&0&1&0&0&0\
0&0&0&0&0&0&1&0\
0&0&0&0&0&0&0&1
endbmatrix$$
Intuitively, this unitary is constructed with two CNOT gates, which swap the third qubit $|0rangleto|1rangle$ or $|1rangleto|0rangle$ if and only if one of the first two qubits is in a $|1rangle$ state:

You can check that multiplying the matrices of the two CNOTs indeed gives the same $rm U_f$.

All quantum operators must be unitary. Unitary means the conjugate-transpose of the operator is its inverse. In your case:

$UU^dagger = beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 1 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix
beginbmatrix
1 & 0 & 0 & 0\
0 & 1 & 0 & 0\
0 & 1 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix =
beginbmatrix
1 & 0 & 0 & 0\
0 & 2 & 0 & 0\
0 & 0 & 0 & 0\
0 & 0 & 0 & 0
endbmatrix$

So it is most certainly not unitary because $UU^dagger neq mathbbI_4$ (same as your second attempt).

There's a long way to construct functions like this, and a short way. The long way is to write out all inputs and outputs:

$U|000rangle = |000rangle$

$U|001rangle = |001rangle$

$U|010rangle = |011rangle$

$U|011rangle = |010rangle$

$U|100rangle = |101rangle$

$U|101rangle = |100rangle$

$U|110rangle = |110rangle$

$U|111rangle = |111rangle$

You can then pretty easily construct the operator from this.

An easier way is to use projection operators & matrix addition to implement "if-then" semantics with matrices:

$U = |00ranglelangle00| otimes mathbbI_2 + |01ranglelangle01|otimes X_2 + |10ranglelangle10| otimes X_2 + |11ranglelangle11|otimes mathbbI_2$

The way to read this is "if the input is $|00rangle$ or $|11rangle$, do not flip the third bit. If the input is $|01rangle$ or $|10rangle$, flip the third bit. $|phiranglelangle phi|$ is called the outer product, and is defined for example as follows:

$|0ranglelangle0| = beginbmatrix 1 \ 0 endbmatrix beginbmatrix 1 & 0 endbmatrix = beginbmatrix 1 & 0 \ 0 & 0 endbmatrix$

which is called a projection operator. Use projection operators to only apply an operation on specific states - here, $|0rangle$.

A huge benefit of this projectors & addition approach is that you never have to actually write out the full matrix, which can become enormous as the number of qbits increase - 3-qbit 8x8 matrices already have 64 elements! This is your first step into using symbolic rather than matrix reasoning. For example, we can use the rules of linear algebra to calculate the action of our $U$ on some input:

$U|101rangle = (|00ranglelangle00| otimes mathbbI_2 + |01ranglelangle01|otimes X_2 + |10ranglelangle10| otimes X_2 + |11ranglelangle11|otimes mathbbI_2)|101rangle$

Now, matrix multiplication distributes over addition. This means we have:

$|00ranglelangle00| otimes mathbbI_2 |101rangle + |01ranglelangle01|otimes X_2 |101rangle + |10ranglelangle10| otimes X_2 |101rangle + |11ranglelangle11|otimes mathbbI_2 |101rangle$

Let's apply further transformation rules. Note $|101rangle = |10rangle otimes |1rangle$, and $(Uotimes V)(|xrangle otimes |yrangle) = U|xrangle otimes V|yrangle$, where in our cases (for example) $U = |00ranglelangle00|$, $V = mathbbI_2$, $x=|10rangle$ and $y=|1rangle$:

$|00ranglelangle00|10rangle otimes mathbbI_2 |1rangle + |01ranglelangle01|10rangle otimes X_2 |1rangle + |10ranglelangle10|10rangle otimes X_2 |1rangle + |11ranglelangle11|10rangle otimes mathbbI_2 |1rangle$

Now, note we have the following four terms:

$langle00|10rangle, langle01|10rangle, langle10|10rangle, langle11|10rangle$

These are called inner products, or dot products and here all of them are zero except for $langle10|10rangle$ - the dot product of $|10rangle$ with itself:

$langle10|10rangle = beginbmatrix 0 & 0 & 1 & 0endbmatrix
beginbmatrix0 \ 0 \ 1 \ 0endbmatrix = 1$

Since the other terms are all zero, they all cancel out:

$requirecancel cancel + cancel + |10ranglecdot 1 otimes X_2 |1rangle + cancel11ranglecdot 0 otimes mathbbI_2 $

So we are left with:

$|10rangle otimes X_2 |1rangle$

Where of course $X_2|1rangle = |0rangle$, so:

$|10rangle otimes |0rangle = |100rangle$

And we calculated $U|101rangle = |100rangle$ as expected, without once having to write out a huge inconvenient matrix!

Your bit strings x in the case when you specify 2 bits are 00, 01, 10, 11.
Now you want to output the result in another bit/qubit.

Whether the outpit bit/qubit is initialized as 0 or 1 should not change your unitary operation. The only thing changing is the initial quantum state your system is onto where you apply the unitary operation representing your function.

In this case, the implementation is straightforward. This is a first CNOT with first qubit of register x as control and the output qubit as target followed by another CNOT with the second qubit of x as control. If you input x=00, nothing happens. If x=01 or 10, you apply one CNOT which adds 1 to the target (definition of CNOT). If x=11, the two CNOTs are applied so you add 1 to the target twice and 1 + 1 = 0 when having one output bit.

To get the unitary, you can just take the unitary matrix of the CNOT, tensor product with the identity matrix (but respect the order when you write). You do this for the first CNOT giving you one unitary $U_1$, then the second giving $ U_2 $ and finally multiply $ U_2 * U_1 $ to get your unitary operator.