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

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

• What is the context of all of this? – user1271772 Oct 18 '18 at 21:50
• Your matrices are wrong. For the first one, the last column is missing a non-zero entry. The top-right cell should be 1 because that's the 3->0 cell and f(3) = 0. – Craig Gidney Oct 18 '18 at 21:53
• @user1271772 The context is educational. I want to know how to do this thing. I need to do it to get there. So I'm doing it: I thought up a simple function and want to see what its matrix would look like and what its circuit would look like. I wasn't making sense of myself so I asked for help. – R. Chopin Oct 21 '18 at 14:08
• Sorry, but why f(2) = 1 if 2 is even? – Fernando Mar 23 at 7:33

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!

• Beautiful lecture. I'm at the right moment to get it! Thank you. – R. Chopin Oct 20 '18 at 16:02
• The point of this operator $U$ is to implement $f$. With that in mind, I must tell users of this operator that they must initialize their second register $|y\rangle$ to $|0\rangle$. Otherwise they'll get wrong parity calculations such as $U|101\rangle = |100\rangle$. I say this is wrong because the parity of $10$ is $1$ and not $0$ as could be inferred from the output without noticing the third q-bit of the input was $|1\rangle$. (This has to be written in the documentation so that users don't trust the operator blindly unless they prepare the input properly.) – R. Chopin Oct 20 '18 at 16:06
• $\newcommand{\ket}[1]{|#1\rangle}$I also see that another possibility is this. Let users initialize their second register to either $\ket{0}$ or $\ket{1}$ but tell them that to get the desired answer --- which is the value of $f(x)$ --- they must compute $M\ket{y_\text{in}} \oplus M\ket{y_\text{out}}$, where $M$ is a measurement operator. – R. Chopin Oct 23 '18 at 12:42

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

• Note this manifestly generalizes if you make x , d bits instead. You just have a CNOT for each of the d. In fact if you break this circuit, you see the parity of the first k bits for one part and the last d-k for the other. – AHusain Oct 19 '18 at 3:14
• $\newcommand{\qr}[1]{|#1\rangle}$Thank you so much for this lecture! Thanks for the "entirely left to us" comment: different from you, I tried to leave the output completely alone if the third q-bit of the input was $\qr{1}$. This fails because we end up with a non-reversible operator. Specifically, $U_f\qr{010} \to \qr{011}$ and also $U_f\qr{011} \to \qr{011}$, a non-injective function. I suppose that's the $\oplus$ makes sure to avoid in the definition of an operator that implements a function $f$. – R. Chopin Oct 20 '18 at 16:15
• Yeah, I forgot to mention it's up to us as long as the operator remains unitary. Just added that in an edit. – Dyon J Don Kiwi van Vreumingen Oct 20 '18 at 22:31

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.

• Very nice lecture. I am also interested in knowing how to build circuits and you do explain that pretty nicely. In particular, you show how I could break the job into two parts, $U_1$ and $U_2$, composing them to get the desired result. Well done! Thank you. – R. Chopin Oct 20 '18 at 16:20
• $\newcommand{\qr}[1]{|#1\rangle}$ Actually I haven't made it to verify this. We have three q-bits involved here --- call them $\qr{x}, \qr{y}, \qr{z}$ where $\qr{x}$ is on the top wire and $\qr{z}$, on the bottom wire. I can get the unitary of the second CNOT: $I_2 \otimes CNOT$ where I_2 represents doing nothing to $\qr{x}$. But how can I get the first unitary if the control q-bit is $\qr{x}$ and the target is $\qr{z}$. It's as if I needed to tensor product $I_2$ in the middle. I don't know what to do here. I'd appreciate if you expand your answer to as to take this into account. – R. Chopin Oct 23 '18 at 18:47
• @R.Chopin Done :) – cnada Oct 24 '18 at 3:38