How to derive the CNOT matrix for a 3-qbit system where the control & target qbits are not adjacent?
In a three-qbit system, it's easy to derive the CNOT operator when the control & target qbits are adjacent in significance - you just tensor the 2-bit CNOT operator with the identity matrix in the untouched qbit'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 qbits are not adjacent in significance:
$C_{20}|\phi_2\phi_1\phi_0\rangle$
How is this done?
quantum-gate gate-synthesis
Sanchayan Dutta
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.
Niel de BeaudrapNiel de Beaudrap
$\begingroup$ Oh yeah, I recall projectors from early on in the Mermin book. Projectors and matrix addition are a way of encoding conditional logic in matrices! $\endgroup$ – ahelwer Sep 19 '18 at 22:39
$\begingroup$ "a simple change in representation is unlikely to make a difficult quantum algorithm efficiently solvable" - what about in the case of wick rotation's? $\endgroup$ – meowzz Oct 4 '18 at 17:08
$\begingroup$ @meowzz: Every once in a while, such a change in notation allows you to make a conceptual advance and helps you to solve problems more easily. But not often, and probably not in the case of this particular change of notation, which is reasonably well-known. As to the specific case of the Wick rotation, however, the question I would ask is what specific advance it made possible to solve problems, and what problems it was helpful for. $\endgroup$ – Niel de Beaudrap Oct 4 '18 at 17:15
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 110 \rangle \mapsto \lvert 111 \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.
Ryan O'DonnellRyan O'Donnell
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}
JitendraJitendra
Not the answer you're looking for? Browse other questions tagged quantum-gate gate-synthesis or ask your own question.
Matrix representation and CX gate
How are multi-qubit gates extended into larger registers?
Given a decomposition for a unitary $U$, how do you decompose the corresponding controlled unitary gate $C(U)$?
Does quantum control allow to implement any gate?
How do we code the matrix for a controlled operation knowing the control qubit, the target qubit and the $2\times 2$ unitary?
Why is the CNOT gate matrix a valid representation for two-qubit states?
A quantum circuit with entanglement with Eve
How to construct matrix of regular and "flipped" 2-qubit CNOT?
Implementing these $N×N$ matrices on $\log N$ qubits
Quantum Toffoli gate equation
Are these notations for the CCNOT gate with different controls correct?