Iyfjky

Question

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_2phi_1phi_0rangle = (mathbbI_2 otimes C_10)|phi_2phi_1phi_0rangle$

However, it isn't obvious how to derive the CNOT operator when the control & target qbits are not adjacent in significance:

$C_20|phi_2phi_1phi_0rangle$

How is this done?

score 1 · Accepted Answer · 2018-09-18 20:57:08Z

For a presentation from first principles, I like Ryan O'Donnel'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:
$$ mathitCU ;=; defket#1lvert #1 rangledefbra#1langle #1 rvertket0!bra0 !otimes! mathbf 1 ,+, ket1!bra1 !otimes! U$$
where $mathbf 1$ is an identity matrix of the same dimension as $U$. Here, $ket0!bra0$ and $ket1!bra1$ are projectors onto the states $ket0$ and $ket1$ 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 $mathitCX_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:
$$
beginaligned
mathitCX_1,3 ;&=;
ket0!bra0 otimes mathbf 1_4 ,+, ket1!bra1 otimes (mathbf 1_2 otimes X)
\[1ex]&=;
beginbmatrix
mathbf 1_4 & mathbf 0_4 \
mathbf 0_4 & (mathbf 1_2 !otimes! X)
endbmatrix
;=;
beginbmatrix
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
endbmatrix,
endaligned
$$
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
$$
beginalignat2
mathitCX_1,3 ;&=&;
underbraceket0!bra0_textcontrol otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbrace;mathbf 1_2;_!!!!texttarget!!!!
&+,
underbraceket1!bra1_textcontrol otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbrace; X;_!!!!texttarget!!!!
\[1ex]&=&;
beginbmatrix
mathbf 1_2 & mathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
mathbf 0_2 & mathbf 1_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2
endbmatrix
,&+,
beginbmatrix
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & X & mathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & mathbf 0_2 & X
endbmatrix
endalignat
$$
and also allows us to immediately see what to do if the roles of control and target are reversed:
$$
beginalignat2
mathitCX_3,1 ;&=&;
underbrace;mathbf 1_2;_!!!!texttarget!!!! otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbraceket0!bra0_textcontrol
,&+,
underbrace;X;_!!!!texttarget!!!! otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbraceket1!bra1_textcontrol
\[1ex]&=&;
scriptstylebeginbmatrix
!ket0!bra0!! & & & \
& !!ket0!bra0!! & & \
& & !!ket0!bra0!! & \
& & & !!ket0!bra0
endbmatrix
,&+,
scriptstylebeginbmatrix
& & !!ket1!bra1!! & \
& & & !!ket1!bra1 \
!ket1!bra1!! & & & \
& !!ket1!bra1 & &
endbmatrix
\[1ex]&=&;
left[scriptstylebeginmatrix
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
endmatrixright.,,&,,left.scriptstylebeginmatrix
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
endmatrixright].
endalignat
$$
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 $mathitCX_1,3 ,=,
ket0!bra0 otimes mathbf 1_2 otimes mathbf 1_2 ,+,
ket1!bra1 otimes mathbf 1_2 otimes X$
and
$mathitCX_3,1 ,=,
mathbf 1_2 otimes mathbf 1_2 otimes ket0!bra0 ,+,
X otimes mathbf 1_2 otimes ket1!bra1$.
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.

Jitendra 1755 · Answer 2 · 2018-09-18 19:46:59Z

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 $|phirangle=|uparrow_1downarrow_2downarrow_3....uparrow_n-1downarrow_nrangle$. Now you choose your control and target, lets say $i'th$ is control and $k'th$ is target. Applying CNOT on $|phirangle$ will be just
beginequation
CNOT|phirangle=CNOT|uparrow_1downarrow_2...uparrow_i...uparrow_k...uparrow_n-1downarrow_nrangle= |uparrow_1downarrow_2...uparrow_i...downarrow_k...uparrow_n-1downarrow_nrangle
endequation

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$($2times2$ Identity) if $i'th$ state is down. We apply these matrices at the $k'th$ position, which is our target. Mathematically,
beginequation
CNOT = Big[|uparrow_1...uparrow_i...uparrow_k-1ranglelangleuparrow_1...uparrow_i...uparrow_k-1|otimessigma_xotimes|uparrow_k+1...uparrow_nranglelangleuparrow_k+1...uparrow_n| + all permutations of states other then i'thBig]
+ Big[|uparrow_1...downarrow_i...uparrow_k-1ranglelangleuparrow_1...downarrow_i...uparrow_k-1|otimes Iotimes|uparrow_k+1...uparrow_nranglelangleuparrow_k+1...uparrow_n| + all permutations of states other then i'thBig]
endequation

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.

Ryan O'Donnell 1112 · Answer 3 · 2018-09-18 19:56:38Z

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 000rangle mapsto lvert 000rangle$

$lvert 001rangle mapsto lvert 001rangle$

$lvert 010rangle mapsto lvert 010rangle$

$lvert 011rangle mapsto lvert 011rangle$

$lvert 100rangle mapsto lvert 101rangle$

$lvert 101rangle mapsto lvert 100rangle$

$lvert 110 rangle mapsto lvert 111 rangle$

$lvert 111 rangle mapsto lvert 110 rangle$

and therefore it is given by the following matrix:

$U = beginbmatrix
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
endbmatrix$

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

score 1 · Accepted Answer · 2018-09-18 20:57:08Z

For a presentation from first principles, I like Ryan O'Donnel'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:
$$ mathitCU ;=; defket#1lvert #1 rangledefbra#1langle #1 rvertket0!bra0 !otimes! mathbf 1 ,+, ket1!bra1 !otimes! U$$
where $mathbf 1$ is an identity matrix of the same dimension as $U$. Here, $ket0!bra0$ and $ket1!bra1$ are projectors onto the states $ket0$ and $ket1$ 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 $mathitCX_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:
$$
beginaligned
mathitCX_1,3 ;&=;
ket0!bra0 otimes mathbf 1_4 ,+, ket1!bra1 otimes (mathbf 1_2 otimes X)
\[1ex]&=;
beginbmatrix
mathbf 1_4 & mathbf 0_4 \
mathbf 0_4 & (mathbf 1_2 !otimes! X)
endbmatrix
;=;
beginbmatrix
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
endbmatrix,
endaligned
$$
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
$$
beginalignat2
mathitCX_1,3 ;&=&;
underbraceket0!bra0_textcontrol otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbrace;mathbf 1_2;_!!!!texttarget!!!!
&+,
underbraceket1!bra1_textcontrol otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbrace; X;_!!!!texttarget!!!!
\[1ex]&=&;
beginbmatrix
mathbf 1_2 & mathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
mathbf 0_2 & mathbf 1_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2
endbmatrix
,&+,
beginbmatrix
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 & phantommathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & X & mathbf 0_2 \
phantommathbf 0_2 & phantommathbf 0_2 & mathbf 0_2 & X
endbmatrix
endalignat
$$
and also allows us to immediately see what to do if the roles of control and target are reversed:
$$
beginalignat2
mathitCX_3,1 ;&=&;
underbrace;mathbf 1_2;_!!!!texttarget!!!! otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbraceket0!bra0_textcontrol
,&+,
underbrace;X;_!!!!texttarget!!!! otimes underbrace;mathbf 1_2;_!!!!textuninvolved!!!! otimes underbraceket1!bra1_textcontrol
\[1ex]&=&;
scriptstylebeginbmatrix
!ket0!bra0!! & & & \
& !!ket0!bra0!! & & \
& & !!ket0!bra0!! & \
& & & !!ket0!bra0
endbmatrix
,&+,
scriptstylebeginbmatrix
& & !!ket1!bra1!! & \
& & & !!ket1!bra1 \
!ket1!bra1!! & & & \
& !!ket1!bra1 & &
endbmatrix
\[1ex]&=&;
left[scriptstylebeginmatrix
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
endmatrixright.,,&,,left.scriptstylebeginmatrix
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
endmatrixright].
endalignat
$$
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 $mathitCX_1,3 ,=,
ket0!bra0 otimes mathbf 1_2 otimes mathbf 1_2 ,+,
ket1!bra1 otimes mathbf 1_2 otimes X$
and
$mathitCX_3,1 ,=,
mathbf 1_2 otimes mathbf 1_2 otimes ket0!bra0 ,+,
X otimes mathbf 1_2 otimes ket1!bra1$.
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.

Jitendra 1755 · Answer 5 · 2018-09-18 19:46:59Z

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 $|phirangle=|uparrow_1downarrow_2downarrow_3....uparrow_n-1downarrow_nrangle$. Now you choose your control and target, lets say $i'th$ is control and $k'th$ is target. Applying CNOT on $|phirangle$ will be just
beginequation
CNOT|phirangle=CNOT|uparrow_1downarrow_2...uparrow_i...uparrow_k...uparrow_n-1downarrow_nrangle= |uparrow_1downarrow_2...uparrow_i...downarrow_k...uparrow_n-1downarrow_nrangle
endequation

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$($2times2$ Identity) if $i'th$ state is down. We apply these matrices at the $k'th$ position, which is our target. Mathematically,
beginequation
CNOT = Big[|uparrow_1...uparrow_i...uparrow_k-1ranglelangleuparrow_1...uparrow_i...uparrow_k-1|otimessigma_xotimes|uparrow_k+1...uparrow_nranglelangleuparrow_k+1...uparrow_n| + all permutations of states other then i'thBig]
+ Big[|uparrow_1...downarrow_i...uparrow_k-1ranglelangleuparrow_1...downarrow_i...uparrow_k-1|otimes Iotimes|uparrow_k+1...uparrow_nranglelangleuparrow_k+1...uparrow_n| + all permutations of states other then i'thBig]
endequation

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.

Ryan O'Donnell 1112 · Answer 6 · 2018-09-18 19:56:38Z

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 000rangle mapsto lvert 000rangle$

$lvert 001rangle mapsto lvert 001rangle$

$lvert 010rangle mapsto lvert 010rangle$

$lvert 011rangle mapsto lvert 011rangle$

$lvert 100rangle mapsto lvert 101rangle$

$lvert 101rangle mapsto lvert 100rangle$

$lvert 110 rangle mapsto lvert 111 rangle$

$lvert 111 rangle mapsto lvert 110 rangle$

and therefore it is given by the following matrix:

$U = beginbmatrix
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
endbmatrix$

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

Search This Blog

Iyfjky

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

3 Answers
3

Your Answer

Post as a guest

3 Answers
3

3 Answers
3

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

Category

Random preview

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

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Confectionery

3 Answers
3

3 Answers
3

3 Answers
3

Long meetings (6-7 hours a day): Being â€œbabysatâ€ by supervisor