What is the matrix for the operator that implements a function to tell the parity of its argument?

Question

$\newcommand{\qr}[1]{|#1\rangle}$ 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_f\qr{x}_2 \qr{0}_1 \to \qr{x}_2\qr{0 \oplus f(x)}_1$. After doing my calculations, I think the following matrix represents $U_f$

$$\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \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 $\qr{x}_2\qr{1}$. (I'm not too clear on that.)

So --- though confused ---, I went ahead and defined $$U_f\qr{x}_2 \qr{1}_1 \to \qr{x}_2\qr{1 \oplus f(x)}_1.$$ Doing my calculations again, I get the following matrix

$$\begin{bmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \otimes I_2$$

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

Answer 1

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

$UU^{\dagger} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}$

So it is most certainly not unitary because $UU^{\dagger} \neq \mathbb{I}_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|000\rangle = |000\rangle$

$U|001\rangle = |001\rangle$

$U|010\rangle = |011\rangle$

$U|011\rangle = |010\rangle$

$U|100\rangle = |101\rangle$

$U|101\rangle = |100\rangle$

$U|110\rangle = |110\rangle$

$U|111\rangle = |111\rangle$

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 = |00\rangle\langle00| \otimes \mathbb{I}_2 + |01\rangle\langle01|\otimes X_2 + |10\rangle\langle10| \otimes X_2 + |11\rangle\langle11|\otimes \mathbb{I}_2$

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

$|0\rangle\langle0| = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$

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

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|101\rangle = (|00\rangle\langle00| \otimes \mathbb{I}_2 + |01\rangle\langle01|\otimes X_2 + |10\rangle\langle10| \otimes X_2 + |11\rangle\langle11|\otimes \mathbb{I}_2)|101\rangle$

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

$|00\rangle\langle00| \otimes \mathbb{I}_2 |101\rangle + |01\rangle\langle01|\otimes X_2 |101\rangle + |10\rangle\langle10| \otimes X_2 |101\rangle + |11\rangle\langle11|\otimes \mathbb{I}_2 |101\rangle$

Let's apply further transformation rules. Note $|101\rangle = |10\rangle \otimes |1\rangle$, and $(U\otimes V)(|x\rangle \otimes |y\rangle) = U|x\rangle \otimes V|y\rangle$, where in our cases (for example) $U = |00\rangle\langle00|$, $V = \mathbb{I}_2$, $x=|10\rangle$ and $y=|1\rangle$:

$|00\rangle\langle00|10\rangle \otimes \mathbb{I}_2 |1\rangle + |01\rangle\langle01|10\rangle \otimes X_2 |1\rangle + |10\rangle\langle10|10\rangle \otimes X_2 |1\rangle + |11\rangle\langle11|10\rangle \otimes \mathbb{I}_2 |1\rangle$

Now, note we have the following four terms:

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

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

$\langle10|10\rangle = \begin{bmatrix} 0 & 0 & 1 & 0\end{bmatrix} \begin{bmatrix}0 \\ 0 \\ 1 \\ 0\end{bmatrix} = 1$

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

$\require{cancel} \cancel{|00\rangle\cdot 0 \otimes \mathbb{I}_2 |1\rangle} + \cancel{|01\rangle\cdot 0 \otimes X_2 |1\rangle} + |10\rangle\cdot 1 \otimes X_2 |1\rangle + \cancel{|11\rangle\cdot 0 \otimes \mathbb{I}_2 |1\rangle}$

So we are left with:

$|10\rangle \otimes X_2 |1\rangle$

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

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

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

Answer 2

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}{}^\dagger{\rm 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|000\rangle=|000\rangle\\ {\rm U}_f|010\rangle=|011\rangle\\ {\rm U}_f|100\rangle=|101\rangle\\ {\rm U}_f|110\rangle=|110\rangle$$ 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, $|\!*\!*1\rangle$. How we do this is entirely up to us! (As long as ${\rm U}_f$ remains unitary, of course.) So we can just choose something convenient, such as this: $${\rm U}_f|001\rangle=|001\rangle\\ {\rm U}_f|011\rangle=|010\rangle\\ {\rm U}_f|101\rangle=|100\rangle\\ {\rm U}_f|111\rangle=|111\rangle$$ This has the following matrix form: $${\rm U}_f=\begin{bmatrix} 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 \end{bmatrix}$$ Intuitively, this unitary is constructed with two CNOT gates, which swap the third qubit $|0\rangle\to|1\rangle$ or $|1\rangle\to|0\rangle$ if and only if one of the first two qubits is in a $|1\rangle$ state:

You can check that multiplying the matrices of the two CNOTs indeed gives the same ${\rm U}_f$.

Answer 3

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.

There is another way to get unitary operator which is more useful when dealing with controlled-gates in a multi-qubit system. For example, can also be written as : $$ |0\rangle\langle 0|\otimes\mathbb{I}+|1\rangle\langle 1|\otimes U $$

It is like a sort of quantum if statement. Basically, if the control is 0, do nothing, otherwise apply U. Using this definition on your example, it follows that :

$$ |0\rangle\langle 0|\otimes\mathbb{I} \otimes\mathbb{I} +|1\rangle\langle 1| \otimes\mathbb{I}\otimes X $$ where X is the NOT gate.

You have an example on a 5-qubit system in this blog. Also, I asked a similar question in the past but for a code of such operation.