How to derive the CNOT matrix for a 3-qubit system where the control & target qubits are not adjacent?

Question

In a three-qubit system, it's easy to derive the CNOT operator when the control & target qubits are adjacent in significance - you just tensor the 2-bit CNOT operator with the identity matrix in the untouched qubit's position of significance:

$$C_{10}|\phi_2\phi_1\phi_0\rangle = (\mathbb{I}_2 \otimes C_{10})|\phi_2\phi_1\phi_0\rangle.$$

However, it isn't obvious how to derive the CNOT operator when the control & target qubits are not adjacent in significance: $C_{20}|\phi_2\phi_1\phi_0\rangle.$

How is this done?

Answer 1

For a presentation from first principles, I like Ryan O'Donnell's answer. But for a slightly higher-level algebraic treatment, here's how I would do it.

The main feature of a controlled-$U$ operation, for any unitary $U$, is that it (coherently) performs an operation on some qubits depending on the value of some single qubit. The way that we can write this explicitly algebraically (with the control on the first qubit) is: $$ \mathit{CU} \;=\; \def\ket#1{\lvert #1 \rangle}\def\bra#1{\langle #1 \rvert}\ket{0}\!\bra{0} \!\otimes\! \mathbf 1 \,+\, \ket{1}\!\bra{1} \!\otimes\! U$$ where $\mathbf 1$ is an identity matrix of the same dimension as $U$. Here, $\ket{0}\!\bra{0}$ and $\ket{1}\!\bra{1}$ are projectors onto the states $\ket{0}$ and $\ket{1}$ of the control qubit — but we are not using them here as elements of a measurement, but to describe the effect on the other qubits depending on one or the other subspace of the state-space of the first qubit.

We can use this to derive the matrix for the gate $\mathit{CX}_{1,3}$ which performs an $X$ operation on qubit 3, coherently conditioned on the state of qubit 1, by thinking of this as a controlled-$(\mathbf 1_2 \!\otimes\! X)$ operation on qubits 2 and 3: $$ \begin{aligned} \mathit{CX}_{1,3} \;&=\; \ket{0}\!\bra{0} \otimes \mathbf 1_4 \,+\, \ket{1}\!\bra{1} \otimes (\mathbf 1_2 \otimes X) \\[1ex]&=\; \begin{bmatrix} \mathbf 1_4 & \mathbf 0_4 \\ \mathbf 0_4 & (\mathbf 1_2 \!\otimes\! X) \end{bmatrix} \;=\; \begin{bmatrix} \mathbf 1_2 & \mathbf 0_2 & \mathbf 0_2 & \mathbf 0_2 \\ \mathbf 0_2 & \mathbf 1_2 & \mathbf 0_2 & \mathbf 0_2 \\ \mathbf 0_2 & \mathbf 0_2 & X & \mathbf 0_2 \\ \mathbf 0_2 & \mathbf 0_2 & \mathbf 0_2 & X \end{bmatrix}, \end{aligned} $$ where the latter two are block matrix representations to save on space (and sanity).

Better still: we can recognise that — on some mathematical level where we allow ourselves to realise that the order of the tensor factors doesn't have to be in some fixed order — the control and the target of the operation can be on any two tensor factors, and that we can fill in the description of the operator on all of the other qubits with $\mathbf 1_2$. This would allow us to jump straight to the representation $$ \begin{alignat}{2} \mathit{CX}_{1,3} \;&=&\; \underbrace{\ket{0}\!\bra{0}}_{\text{control}} \otimes \underbrace{\;\mathbf 1_2\;}_{\!\!\!\!\text{uninvolved}\!\!\!\!} \otimes \underbrace{\;\mathbf 1_2\;}_{\!\!\!\!\text{target}\!\!\!\!} &+\, \underbrace{\ket{1}\!\bra{1}}_{\text{control}} \otimes \underbrace{\;\mathbf 1_2\;}_{\!\!\!\!\text{uninvolved}\!\!\!\!} \otimes \underbrace{\; X\;}_{\!\!\!\!\text{target}\!\!\!\!} \\[1ex]&=&\; \begin{bmatrix} \mathbf 1_2 & \mathbf 0_2 & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} \\ \mathbf 0_2 & \mathbf 1_2 & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} \\ \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} \\ \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} \end{bmatrix} \,&+\, \begin{bmatrix} \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} \\ \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} \\ \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & X & \mathbf 0_2 \\ \phantom{\mathbf 0_2} & \phantom{\mathbf 0_2} & {\mathbf 0_2} & X \end{bmatrix} \end{alignat} $$ and also allows us to immediately see what to do if the roles of control and target are reversed: $$ \begin{alignat}{2} \mathit{CX}_{3,1} \;&=&\; \underbrace{\;\mathbf 1_2\;}_{\!\!\!\!\text{target}\!\!\!\!} \otimes \underbrace{\;\mathbf 1_2\;}_{\!\!\!\!\text{uninvolved}\!\!\!\!} \otimes \underbrace{\ket{0}\!\bra{0}}_{\text{control}} \,&+\, \underbrace{\;X\;}_{\!\!\!\!\text{target}\!\!\!\!} \otimes \underbrace{\;\mathbf 1_2\;}_{\!\!\!\!\text{uninvolved}\!\!\!\!} \otimes \underbrace{\ket{1}\!\bra{1}}_{\text{control}} \\[1ex]&=&\; {\scriptstyle\begin{bmatrix} \!\ket{0}\!\bra{0}\!\! & & & \\ & \!\!\ket{0}\!\bra{0}\!\! & & \\ & & \!\!\ket{0}\!\bra{0}\!\! & \\ & & & \!\!\ket{0}\!\bra{0} \end{bmatrix}} \,&+\, {\scriptstyle\begin{bmatrix} & & \!\!\ket{1}\!\bra{1}\!\! & \\ & & & \!\!\ket{1}\!\bra{1} \\ \!\ket{1}\!\bra{1}\!\! & & & \\ & \!\!\ket{1}\!\bra{1} & & \end{bmatrix}} \\[1ex]&=&\; \left[{\scriptstyle\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}}\right.\,\,&\,\,\left.{\scriptstyle\begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}}\right]. \end{alignat} $$ But best of all: if you can write down these operators algebraically, you can take the first steps towards dispensing with the giant matrices entirely, instead reasoning about these operators algebraically using expressions such as $\mathit{CX}_{1,3} = \ket{0}\!\bra{0} \! \otimes\!\mathbf 1_2\! \otimes\! \mathbf 1_2 + \ket{1}\!\bra{1} \! \otimes\! \mathbf 1_2 \! \otimes\! X$ and $\mathit{CX}_{3,1} = \mathbf 1_2 \! \otimes\! \mathbf 1_2 \! \otimes \! \ket{0}\!\bra{0} + X \! \otimes\! \mathbf 1_2 \! \otimes \! \ket{1}\!\bra{1}$. There will be a limit to how much you can do with these, of course — a simple change in representation is unlikely to make a difficult quantum algorithm efficiently solvable, let alone tractable by manual calculation — but you can reason about simple circuits much more effectively using these expressions than with giant space-eating matrices.

Answer 2

This is a good question; it's one that textbooks seem to sneak around. I reached this exact question when preparing a quantum computing lecture a couple days ago.

As far as I can tell, there's no way of getting the desired 8x8 matrix using the Kronecker product $\otimes$ notation for matrices. All you can really say is: Your operation of applying CNOT to three qubits, with the control being the first and the target being the third, has the following effects:

$\lvert 000\rangle \mapsto \lvert 000\rangle$

$\lvert 001\rangle \mapsto \lvert 001\rangle$

$\lvert 010\rangle \mapsto \lvert 010\rangle$

$\lvert 011\rangle \mapsto \lvert 011\rangle$

$\lvert 100\rangle \mapsto \lvert 101\rangle$

$\lvert 101\rangle \mapsto \lvert 100\rangle$

$\lvert 110 \rangle \mapsto \lvert 111 \rangle$

$\lvert 111 \rangle \mapsto \lvert 110 \rangle$

and therefore it is given by the following matrix:

$U = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 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 \end{bmatrix}$

This matrix $U$ is indeed neither $I_2 \otimes \mathrm{CNOT}$ nor $\mathrm{CNOT} \otimes I_2$. There is no succinct Kronecker-product-based notation for it; it just is what it is.

Answer 3

You can also derive CNOT gates that traverse multiple qubits by combining a normal CNOT gate with SWAP gate(s).

Here is the SWAP gate:

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

https://en.wikipedia.org/wiki/Quantum_logic_gate#Swap_gate

All you have to do is repeatedly apply the SWAP gate to one qubit, to get the two qubits next to each other, then apply the CNOT gate, then re-apply SWAP gates to the get the qubit you moved back to its original position.

Answer 4

As a general idea CNOT flips target based on control. I choose to flip the target if control is $\uparrow (= [1\ 0]^T)$, you may choose it $\downarrow (= [0\ 1]^T)$ too. So assume any general multiparticle state $|\phi\rangle=|\uparrow_1\downarrow_2\downarrow_3....\uparrow_{n-1}\downarrow_n\rangle$. Now you choose your control and target, lets say $i'th$ is control and $k'th$ is target. Applying CNOT on $|\phi\rangle$ will be just \begin{equation} CNOT|\phi\rangle=CNOT|\uparrow_1\downarrow_2...\uparrow_i...\uparrow_k...\uparrow_{n-1}\downarrow_n\rangle= |\uparrow_1\downarrow_2...\uparrow_i...\downarrow_k...\uparrow_{n-1}\downarrow_n\rangle \end{equation}

To construct the matrix of such CNOT gate we apply $\sigma_x$($x$-Pauli matrix) if $i'th$ state is up and we apply $I$($2\times2$ Identity) if $i'th$ state is down. We apply these matrices at the $k'th$ position, which is our target. Mathematically, \begin{equation} CNOT = \Big[|\uparrow_1...\uparrow_i...\uparrow_{k-1}\rangle\langle\uparrow_1...\uparrow_i...\uparrow_{k-1}|\otimes\sigma_x\otimes|\uparrow_{k+1}...\uparrow_n\rangle\langle\uparrow_{k+1}...\uparrow_n| + all\ permutations\ of\ states\ other\ then\ i'th\Big] + \Big[|\uparrow_1...\downarrow_i...\uparrow_{k-1}\rangle\langle\uparrow_1...\downarrow_i...\uparrow_{k-1}|\otimes I\otimes|\uparrow_{k+1}...\uparrow_n\rangle\langle\uparrow_{k+1}...\uparrow_n| + all\ permutations\ of\ states\ other\ then\ i'th\Big] \end{equation}

Note $k'th$ state(target) is excluded while creating the permutation matrix and at $k'th$ position the operator $\sigma_x$ or $I$ is written.

Take an example of five qubits in which $2^{nd}$ qubit is target and $4^{th}$ is control. Lets build the permutation matrix of $CNOT$. I take, if control is $\uparrow$ flip the target. You can take vice-versa too.

\begin{align} CNOT & = |\uparrow_1\rangle\langle\uparrow_1|\otimes\sigma_x\otimes|\uparrow_3\uparrow_4\uparrow_5\rangle\langle\uparrow_3\uparrow_4\uparrow_5|\\ & +|\uparrow_1\rangle\langle\uparrow_1|\otimes\sigma_x\otimes|\uparrow_3\uparrow_4\downarrow_5\rangle\langle\uparrow_3\uparrow_4\downarrow_5|\\ & +|\uparrow_1\rangle\langle\uparrow_1|\otimes\sigma_x\otimes|\downarrow_3\uparrow_4\uparrow_5\rangle\langle\downarrow_3\uparrow_4\uparrow_5|\\ & +|\uparrow_1\rangle\langle\uparrow_1|\otimes\sigma_x\otimes|\downarrow_3\uparrow_4\downarrow_5\rangle\langle\downarrow_3\uparrow_4\downarrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes\sigma_x\otimes|\uparrow_3\uparrow_4\uparrow_5\rangle\langle\uparrow_3\uparrow_4\uparrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes\sigma_x\otimes|\uparrow_3\uparrow_4\downarrow_5\rangle\langle\uparrow_3\uparrow_4\downarrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes\sigma_x\otimes|\downarrow_3\uparrow_4\uparrow_5\rangle\langle\downarrow_3\uparrow_4\uparrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes\sigma_x\otimes|\downarrow_3\uparrow_4\downarrow_5\rangle\langle\downarrow_3\uparrow_4\downarrow_5|\\ & +|\uparrow_1\rangle\langle\uparrow_1|\otimes I\otimes|\uparrow_3\downarrow_4\uparrow_5\rangle\langle\uparrow_3\downarrow_4\uparrow_5|\\ & +|\uparrow_1\rangle\langle\uparrow_1|\otimes I\otimes|\uparrow_3\downarrow_4\downarrow_5\rangle\langle\uparrow_3\downarrow_4\downarrow_5|\\ & +|\uparrow_1\rangle\langle\uparrow_1|\otimes I\otimes|\downarrow_3\downarrow_4\uparrow_5\rangle\langle\downarrow_3\downarrow_4\uparrow_5|\\ & +|\uparrow_1\rangle\langle\uparrow_1|\otimes I\otimes|\downarrow_3\downarrow_4\downarrow_5\rangle\langle\downarrow_3\downarrow_4\downarrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes I\otimes|\uparrow_3\downarrow_4\uparrow_5\rangle\langle\uparrow_3\uparrow_4\downarrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes I\otimes|\uparrow_3\downarrow_4\downarrow_5\rangle\langle\uparrow_3\downarrow_4\downarrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes I\otimes|\downarrow_3\downarrow_4\uparrow_5\rangle\langle\downarrow_3\downarrow_4\uparrow_5|\\ & +|\downarrow_1\rangle\langle\downarrow_1|\otimes I\otimes|\downarrow_3\downarrow_4\downarrow_5\rangle\langle\downarrow_3\downarrow_4\downarrow_5| \end{align}

Answer 5

firstly write CNOT⊗𝐼2 matrix, then change the order of index2 and index3 with matlab. in this way, you can do any number of qubits.