3.1.6 Controlled-NOT operation

NOT\mathrm{NOT} and SWAP\mathrm{SWAP} operations together can be used to change individual bits and to reorder them in a different order. However, they don’t cause the bits to interact with one another. What we would like is another more sophisticated operation that can change the value of one bit depending on the value of another. The simplest and most important such operation is CNOT\mathrm{CNOT} or the controlled-NOT operation. It flips the target bit if the control bit is set to 11.

When the first bit is the control and the second bit is the target, we will write this operation as CNOT1→2\mathrm{CNOT}_{1\to 2}. In this case:

CNOT1→2⁢[00]\displaystyle\mathrm{CNOT}_{1\to 2}\,[00] =[00],\displaystyle=[00], (3.19)
CNOT1→2⁢[01]\displaystyle\mathrm{CNOT}_{1\to 2}\,[01] =[01],\displaystyle=[01],
CNOT1→2⁢[10]\displaystyle\mathrm{CNOT}_{1\to 2}\,[10] =[11],\displaystyle=[11],
CNOT1→2⁢[11]\displaystyle\mathrm{CNOT}_{1\to 2}\,[11] =[10].\displaystyle=[10].

This amounts to exchanging the strings [10][10] and [11][11] while leaving the other two strings alone.

Another way of thinking about CNOT1→2\mathrm{CNOT}_{1\to 2} is as an addition: it adds the two bits (modulo 22) and stores the result in the second bit. This can be summarized very concisely as follows:

CNOT1→2⁢[a,b]=[a,a⊕b],\mathrm{CNOT}_{1\to 2}\,[a,b]=[a,a\oplus b], (3.20)

for any a,b∈{0,1}a,b\in\{0,1\}, where “⊕\oplus” denotes addition modulo 22 and we use a comma to separate the values of the two bits. The laws for addition modulo 2 are as follows:

0⊕0=1⊕1=0,\displaystyle 0\oplus 0=1\oplus 1=0, 0⊕1=1⊕0=1.\displaystyle 0\oplus 1=1\oplus 0=1. (3.21)

Sometimes “⊕\oplus” is also called XOR or the exclusive OR operation, since the result is 11 when exactly one out of the two bits are 11. As usual, we can extend CNOT1→2\mathrm{CNOT}_{1\to 2} from deterministic to probabilistic bits by linearity.

We will also be interested in controlled-NOT operations where the second bit is the control and the first is the target. In analogy, we will denote this operation by CNOT2→1\mathrm{CNOT}_{2\to 1}.

Exercise 3.4 ( Swapping control and target ).
  1. 1.
    ​

    Write down a formula similar to Eq. 3.20 for CNOT2→1\mathrm{CNOT}_{2\to 1}.

  2. 2.
    ​

    How can CNOT2→1\mathrm{CNOT}_{2\to 1} be implemented using SWAP\mathrm{SWAP} and CNOT1→2\mathrm{CNOT}_{1\to 2}?

Solution.
  1. 1.
    ​

    CNOT2→1⁢[a,b]=[a⊕b,b]=[b⊕a,b]\mathrm{CNOT}_{2\to 1}[a,b]=[a\oplus b,b]=[b\oplus a,b].

  2. 2.
    ​

    This can be done by first applying a SWAP\mathrm{SWAP}, then a CNOT1→2\mathrm{CNOT}_{1\to 2}, and finally another SWAP\mathrm{SWAP}. Indeed, using Eqs. 3.18 and 3.20,

    SWAP⁢(CNOT1→2⁢(SWAP⁢[a,b]))=SWAP⁢(CNOT1→2⁢[b,a])\displaystyle\quad\mathrm{SWAP}(\mathrm{CNOT}_{1\to 2}(\mathrm{SWAP}[a,b]))=% \mathrm{SWAP}(\mathrm{CNOT}_{1\to 2}[b,a])
    =SWAP⁢[b,b⊕a]=[b⊕a,b].\displaystyle=\mathrm{SWAP}[b,b\oplus a]=[b\oplus a,b].

In Quirky, you can build a controlled-NOT operation by the following two-step process. First, drag the ∙\bullet box onto one of the wires – this marks the wire as the control bit. Next, drag the ⊕\oplus box onto the corresponding location on the other wire, marking it as the target bit. A connection will emerge to indicate that you have successfully created a controlled-NOT operation. For example, if we choose the bottom bit as the control and the top bit as the target, we obtain the following result:

[Uncaptioned image]

Remembering that the bottom (!) bit is the first bit and the top bit is the second bit, we see that this corresponds to the CNOT1→2\mathrm{CNOT}_{1\to 2} operation. Here is a more complicated example, where we first apply CNOT1→2\mathrm{CNOT}_{1\to 2} and then CNOT2→1\mathrm{CNOT}_{2\to 1}:

[Uncaptioned image]

Homework 3.2 ( SWAP\mathrm{SWAP} from CNOT\mathrm{CNOT}s ).
[Uncaptioned image]

Problem: It is almost midnight but Bob is still tinkering with his prototype probabilistic bit computer that he wants to present at school the next day. He is so preoccupied with calibrating the randomness generator that he forgot to feed his parrot Ziggy. To attract Bob’s attention, Ziggy knocks off Bob’s coffee cup and spills the coffee all over his custom-made keyboard for activating different operations. Bob is horrified since the SWAP key is no longer working! Luckily, the CNOT key still works. Question: How can Bob implement the SWAP\mathrm{SWAP} operation using only controlled-NOT operations? (If you want to prove that two operations are the same, you only have to show this for the basis states because of extension by linearity.)

Hint: You should use three CNOT operations.

Hack.

This can be done by three controlled-NOT operations, namely:

SWAP=CNOT1→2⁢CNOT2→1⁢CNOT1→2\mathrm{SWAP}=\mathrm{CNOT}_{1\to 2}\mathrm{CNOT}_{2\to 1}\mathrm{CNOT}_{1\to 2}

We can check that this works by checking that indeed these CNOT\mathrm{CNOT}’s send [a,b][a,b] to [b,a][b,a], for all a,b∈{0,1}a,b\in\{0,1\}:

CNOT1→2⁢(CNOT2→1⁢(CNOT1→2⁢[a,b]))\displaystyle\quad\mathrm{CNOT}_{1\to 2}(\mathrm{CNOT}_{2\to 1}(\mathrm{CNOT}_% {1\to 2}[a,b]))
=CNOT1→2⁢(CNOT2→1⁢[a,a⊕b])\displaystyle=\mathrm{CNOT}_{1\to 2}(\mathrm{CNOT}_{2\to 1}[a,a\oplus b])
=CNOT1→2⁢[a⊕a⊕b,a⊕b]\displaystyle=\mathrm{CNOT}_{1\to 2}[a\oplus a\oplus b,a\oplus b]
=CNOT1→2⁢[b,a⊕b]\displaystyle=\mathrm{CNOT}_{1\to 2}[b,a\oplus b]
=[b,a⊕b⊕b]=[b,a],\displaystyle=[b,a\oplus b\oplus b]=[b,a],

where we used the fact that a⊕a=0a\oplus a=0, for any a∈{0,1}a\in\{0,1\}, see Eq. 3.21. This construction is actually very similar to the XOR swap algorithm that one can run on a classical computer. This is a perfect example where knowing how to program a classical computer can help you develop quantum algorithms!