The CCNOT-gate

What if we wanted to apply a certain gate if and only if two other qubits are in-state $|1\rangle$? If you’ve read this course carefully so far, you may object that AND is not a valid qubit gate. A brief look at the truth table discloses that the AND operator is not reversible. If we get false as its output, we can’t tell what the input was. It could be one of three different states.

The $CNOT$-gate provides a way out. Remember, when we constructed the $CR_Y$-gate, we used the $CNOT$-gate to switch the amplitudes of the controlled qubit in the middle of a rotation about the first half and a backward rotation about the second half of the overall rotation. A similar pattern allows us to create a controlled-controlled gate. Such a gate contains an AND relationship because it has two control qubits, and it only changes the target qubit if both control qubits are in-state $|1\rangle$.

The following figure depicts the circuit of the $CCNOT$-gate a controlled-controlled-NOT-gate.

The CCNOT-gate is also known as the Toffoli gate. The Toffoli gate has a different algorithm than this one. The Toffoli gate uses qubit phases. Phases are concepts we cover later in this course. The implementation we presented here is not optimal, but it provides a vivid explanation of the underlying concept.

The following listing depicts the code of this $CCNOT$-gate sequence. We define a reusable function ccnot in line 4. It starts with the controlled rotation with qubit $q_0$​ as the control qubit in line 6. It rotates the controlled qubit about $\theta=\frac{\pi}{2}$, the value we defined earlier in line 2.

We have another controlled rotation with the same qubit as the control qubit in line 11 encapsulated into $CNOT$-gates in lines 10 and 12. It’s important to note that this encapsulated $CR​_Y$​​-gate has $-\theta$ as a parameter. It denotes a rotation in the opposite direction.

Finally, we have another controlled rotation of about $\theta$. Here, qubit $q_1$ is the control qubit.

Let’s go through the circuit one by one. First, we define our $\theta=\frac{\pi}{2}$ in line 2. The value $\frac{\pi}{2}$ represents the rotation about a quarter of the circle. This is half of the overall rotation we want to apply. The rotation about half of the circle ($\pi$) switches the amplitudes from $|0\rangle$ to $|1\rangle$ and vice versa.

In the first step, we rotate the controlled qubit about a quarter circle if qubit $q_1$ is in state $|1\rangle$ through a $CR_Y(\frac{\pi}{2})$-gate in line 15.

The CCNOT‐function

If both control qubits are in-state $|1\rangle$, the result of this gate is as the following figure depicts.

Both control qubits (the upper ones, read right to the left) are in state $|1\rangle$ per our initialization. Then, half the time, as per rotation about $\frac{\pi}{2}$, the controlled qubit is in state $|1\rangle$.

Next, we apply a sequence of a $CNOT$ gate with $q_0$ as the control qubit and $q_1$ as the target qubit. For $q_0$ is in state $|1\rangle$, it changes the state of $q_1$ from $|1\rangle$ to $|0\rangle$. The following controlled rotation with $q_1$ as the control qubit has no effect because $q_1$ is now in state $|0\rangle$ and the ...