How to construct matrix of regular and "flipped" 2-qubit CNOT?

Question

When constructing the matrices for the two CNOT based on the target and control qubit, I can use reasoning:

"If $q_0$==$|0\rangle$, everything simply passes through", resulting in an Identity matrix style $\begin{bmatrix}1&0\\0&1\end{bmatrix}$ in the top left. "If $q_0==|1\rangle$, we need to let $q_0$ pass and swap $q_1$, resulting in a Pauli X $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ in the bottom right.

$CNOT \equiv \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$

"If $q_1$==$|0\rangle$, everything simply passes through", results in leaving $|00\rangle$ and $|10\rangle$ unaffected. "If $q_1==|1\rangle$, we need to let $q_1$ pass and swap $q_0$, mapping $|01\rangle$ to $|11\rangle$ and $|11\rangle$ to $|01\rangle$

$CNOT \equiv \begin{bmatrix}1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0\end{bmatrix}$

This all seems to check out, but here comes my question:
I would like to know if there is a more mathematical way to express this, just as there would be when combining for instance two hadamard gates: $H \otimes H \equiv \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\\ \end{bmatrix} \otimes \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\\ \end{bmatrix} = \frac{1}{2}\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1 \end{bmatrix}$

And a bonus question: How I can, using notation like "CNOT", show which qubit is the control bit and which qubit the target bit?

Answer 1

The CNOT gate is a 2-qubit gate, and consequently, its operation cannot be expressed by the tensor product of two one-qubit gates as the example you gave with the Hadamard gates. An easy way to check that such matrix cannot be expressed as the tensor product of two other matrices is to take matrices

• $A =\begin{pmatrix}a & b \\ c & d\end{pmatrix}$

• $B=\begin{pmatrix}e & f \\ g & h\end{pmatrix}$

and see which values should get the elements of them so that $CNOT = A\otimes B$. Following this reasoning:

$A\otimes B= \begin{pmatrix}ae &af & be & bf \\ ag & ah & bg & bh \\ ce & cf & de & df\\cg & ch & dg & dh\end{pmatrix} $

It is clear that $b=0$ and $c=0$ are needed, as all the elements they affect must be zero, and so $a=1$ and $d=1$ because some of the elements they affect must be non-zero. This leaves last matrix as

$\begin{pmatrix}e &f & 0 & 0 \\ g & h & 0 & 0 \\ 0 & 0 & e & f\\0 & 0 & g & h\end{pmatrix}$.

From this matrix it is pretty straightforward to see that it is not possible to obtain the CNOT matrix, as for example $e=1$ so that the $(1,1)$ element is $1$, but also $e=0$ because the $(3,3)$ element is one; implying a contradiction, and so proving that CNOT cannot be expressed in such a way. The same happens with the other definition of CNOT. From a notation point of view to see which is the target and control qubit I usually use

• $CNOT(1\rightarrow2)=\begin{pmatrix}1 &0& 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\\0 & 0 & 1 & 0\end{pmatrix}$.

• $CNOT(1\leftarrow2)=\begin{pmatrix}1 &0& 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\\0 & 1 & 0 & 0\end{pmatrix}$.

This way it is know that the target qubit is the one being pointed by the arrow. One thing you can express mathematically easily is the relationship between $CNOT(1\rightarrow2)$ and $CNOT(1\leftarrow2)$, which is easily proved to be

$CNOT(1\leftarrow2) = (H\otimes H)CNOT(1\rightarrow 2)(H\otimes H)$.

Answer 2

$$ CNOT = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} $$

But what does this matrix mean? The above matrix means: on a two qubit system (such as $\left|00\right>$, $\left|10\right>$, $\left|11\right>$, etc.) if the first qubit is a one, apply the not gate (X) on the second qubit. That's cool, but what if you have a 4 qubit system $\left(\left|0101\right>\right)$ or an 8 qubit system $\left(\left|00010011\right>\right)$ ? Also, let's say on the 8 qubit system you want to apply the X gate on the 7th qubit if the 2nd is one, how would you go about constructing this matrix?

Cookbook Method

Most books and articles will discuss a cookbook method where you build a matrix based on what the operation does to the base states. Let's work through this for the 2 qubit CNOT gate above. The above gate says if the first qubit is 1 then apply an X to the 2nd qubit. An X just changes the qubit from a 0 to a 1 or a 1 to a 0. The base states for a two qubit system are: $\left|00\right>,\, \left|01\right>,\, \left|10\right>,\, \left|11\right>$

How do I know those are the 4 states? Quantum qubit systems grow as $2^q$ where $q$ is the number of qubits. For a two qubit system $q=2$ therefore there are 4 qubit states. Then you count from 0 to 3 in binary. That is all.

First, this is how CNOT operates on the base states:

$$ CNOT\left|00\right> \rightarrow \left|00\right> $$$$ CNOT\left|01\right> \rightarrow \left|01\right> $$$$ CNOT\left|10\right> \rightarrow \left|11\right> $$$$ CNOT\left|11\right> \rightarrow \left|10\right> $$

To build a matrix you use the following trick:

\begin{align*} CNOT &= \begin{bmatrix}\left<00|CNOT|00\right> && \left<00|CNOT|01\right> && \left<00|CNOT|10\right> && \left<00|CNOT|11\right> \\ \left<01|CNOT|00\right> && \left<01|CNOT|01\right> && \left<01|CNOT|10\right> && \left<01|CNOT|11\right> \\ \left<10|CNOT|00\right> && \left<10|CNOT|01\right> && \left<10|CNOT|10\right> && \left<10|CNOT|11\right> \\ \left<11|CNOT|00\right> && \left<11|CNOT|01\right> && \left<11|CNOT|10\right> && \left<11|CNOT|11\right> \end{bmatrix} \\ \\ &= \begin{bmatrix}\left<00|00\right> && \left<00|01\right> && \left<00|11\right> && \left<00|10\right> \\ \left<01|00\right> && \left<01|01\right> && \left<01|11\right> && \left<01|10\right> \\ \left<10|00\right> && \left<10|01\right> && \left<10|11\right> && \left<10|10\right> \\ \left<11|00\right> && \left<11|01\right> && \left<11|11\right> && \left<11|10\right> \end{bmatrix} \\ \\ &=\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} \end{align*}

This is nice, but now suppose you want a CNOT gate between the 3rd and 9th qubit of a 10 qubit system? You will have $2^{10}$ base states and a $2^{10} \times 2^{10}$ matrix! Good luck with the cookbook method! What we need is an algorithmic method that we can code up in Python.

The Algorithmic Method

A better algorithmic way to think about quantum control gates is by using operators and tensor products. Suppose we have a two qubit system.

To say "If the first qubit is $\left|0\right>$ leave the second qubit alone": $$ \left|0\rangle\langle0\right| \otimes I $$ to leave a qubit alone you apply the Identity operator / matrix $I$

To say "If the first qubit is $\left|1\right>$ apply X to the second qubit":

$$ \left|1\rangle\langle1\right| \otimes X $$

Now put them together by adding them, "If the first qubit is $\left|0\right>$ leave the second qubit alone and If the first qubit is $\left|1\right>$ apply X to the second qubit":

$$ \left|0\rangle\langle0\right| \otimes I + \left|1\rangle\langle1\right| \otimes X $$

In [3]:

from qudotpy import qudot
import numpy as np

zero_matrix = qudot.ZERO.ket * qudot.ZERO.bra
one_matrix = qudot.ONE.ket * qudot.ONE.bra

CNOT = np.kron(zero_matrix, np.eye(2)) + np.kron(one_matrix, qudot.X.matrix)
print(CNOT)

[[ 1.+0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  1.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j  1.+0.j]
 [ 0.+0.j  0.+0.j  1.+0.j  0.+0.j]]

Nice! This is a good algorithmic way to make CNOT gates (or control gates in general). For example, suppose now you want a CNOT gate of a 10 qubit system where the 3rd qubit is the control and the 9th qubit is the target:

"If the third qubit is $\left|0\right>$ leave the ninth qubit alone:" $$ I \otimes I \otimes \left|0\rangle\langle0\right| \otimes I \otimes I \otimes I \otimes I \otimes I \otimes I \otimes I $$

"If the third qubit is $\left|1\right>$ apply X to the ninth qubit": $$ I \otimes I \otimes \left|1\rangle\langle1\right| \otimes I \otimes I \otimes I \otimes I \otimes I \otimes X \otimes I $$

Add those two expression together and you have your 10 qubit CNOT gate.

The above algorithm is straightforward to implement in Python.

Answer 3

I like to use the projectors $$ P_0=|0\rangle\langle 0|\equiv\left(\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array}\right)\qquad P_1=|1\rangle\langle 1|\equiv\left(\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}\right) $$ to express the intuition of the controlled-not when constructing it: $$ CNOT=P_0\otimes\mathbb{I}+P_1\otimes X. $$ Here you can see very plainly the statement "if the first qubit is in $|0\rangle$, do nothing (apply identity) to the second qubit, while if the first qubit is in $|1\rangle$, apply the bit flip". Similarly, the reversed version is $$ \mathbb{I}\otimes P_0+X\otimes P_1. $$

I'm not aware of a standard notation to specify the direction of the controlled-not. Whenever I've needed to do it, I've needed to do it a lot, and went for something very compact: $C^i_j$ to indicate a controlled not controlled by qubit $i$ and targeting qubit $j$. But it's far from standard, so whatever convention you pick, you'd want to state it quite explicitly.