Earlier we mentioned that we could make controlled operations with any number of qubits. By far the most common such gate is the **Toffoli gate**: an extremely important gate in both quantum computing, and the realm of *classical reversible computing*, for which it is a *universal* gate. A computation is reversible if it is possible to run it both forwards and backwards (note that quantum computing is inherently reversible; the operations are unitary, and can be implemented backwards by taking the inverse, which is the adjoint of each operation). For example, a normal AND gate acting on two bits $a$ and $b$ is *not* reversible:

$ab$	$AND(ab)$
00	0
01	0
10	0
11	1

We cannot determine, from the result of AND$(ab),$ what $a$ and $b$ were (unless the result is 1). But by adding another bit to store the result, we can make a reversible AND: the Toffoli. $$ \begin{equation} TOF (abc) = ab (c \oplus ab). \tag{1} \end{equation} $$ The operation keeps the two bits we are taking the AND of intact, and adds the results modulo 2 to a third bit, $c.$ The quantum equivalent of Toffoli acts on the computational basis states in the same way: x $$ TOF|abc\rangle = |ab(c\oplus ab)\rangle. \tag{2} $$ Now, the AND operation only products a non-zero result when the first two bits are 1; when this is true, it adds 1 to the bit $c,$ which is equivalent to performing a NOT gate (flipping the bit). For this reason, the Toffoli is also known as a controlled-controlled-NOT. Instead of controlling on the state of just one qubit, we control on the state of two. That means that the NOT, or $X,$ is applied only if *both* qubits are in the state $\vert 1\rangle.$ Its matrix representation is below: $$ \hbox{TOF} = \begin{pmatrix} 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 & 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\\ \end{pmatrix}. $$ In a circuit, the Toffoli looks like this:

which looks precisely like a controlled-$CNOT.$ --- ***Exercise I.13.4.*** Determine the action of the Toffoli gate on the 3-qubit computational basis states. Look closely at the structure of the qubit states; can you find a mathematical relationship between the first two control bits and the target bit after the operation?

Hint.

We are working with bits, and so are dealing with a Boolean function. Consider which states actually get affected by the Toffoli — what Boolean operation produces a non-zero result only for those states when fed the two control bits? What other Boolean operation can be applied to use that result to modify the target bit?

Solution.

The action of the Toffoli is

$\vert abc\rangle$	$TOF \vert abc\rangle$
$\vert 000\rangle$	$\vert 000\rangle$
$\vert 001\rangle$	$\vert 001\rangle$
$\vert 010\rangle$	$\vert 010\rangle$
$\vert 011\rangle$	$\vert 011\rangle$
$\vert 100\rangle$	$\vert 100\rangle$
$\vert 101\rangle$	$\vert 101\rangle$
$\vert 110\rangle$	$\vert 111\rangle$
$\vert 111\rangle$	$\vert 110\rangle$

If you look closely at the bits, you'll find that $TOF|abc\rangle = |ab(c\oplus ab)\rangle.$ The value of the AND of bits $a$ and $b$ gets added to the third bit modulo 2. ▢

--- As a final point, in a previous section, we discussed quantum circuit synthesis. We now know that $\{CNOT, H, T\}$ is a universal gate set for multi-qubit gates. That means we should be able to decompose gates like the Toffoli down into 1- and 2-qubit gates. Often, this can be done in multiple ways. For example, the following two circuits below both implement the Toffoli:

You can see that each of them require the same number of $T$ gates, however the $T$ depth is different, as are the number of $CNOT$s. The one you would choose if you were implementing a circuit in practice depends on a number of factors, such as how easy it is to perform two-qubit operations in your physical system (if it's hard, better to choose the second implementation since it uses fewer $CNOT$s), or the maximum depth you can implement, if your system is noisy and the qubits have a low *coherence time* (the first circuit has lower depth, so would be better in such a situation). --- ***Exercise I.13.5.*** Another common 3-qubit operation is the controlled-controlled-$Z$ $(CCZ).$

Using what you know about controlled operations, $Z,$ and the Toffoli gate, express the $CCZ$ as a sequence of 1- and 2-qubit operations.

Solution.

We know a decomposition for the Toffoli gate, so if we can re-express $CCZ$ in terms of the Toffoli, then we can recover the decomposition quite easily. Recall that we can express a $CZ$ in terms of $H$ and $CNOT;$ we can extrapolate to the $CCZ$ case:

Thus, we need only take our Toffoli decomposition, and apply a Hadamard on each side. In fact, if you look at both decompositions above, there is already a Hadamard on the third qubit at the start and end of the circuit! These will cancel out, leaving us with the following circuit for $CCZ:$

When working with large quantum circuits, it is often possible to perform small **circuit optimizations** like this, such as cancelling adjacent inverse gates, merging two adjacent rotation gates of the same type, etc. Generally, we would like automated tools to do this for us, though, as the task becomes cumbersome very quickly. ▢

Codercise I.13.1 — The imposter CZ

Codercise I.13.2 — The SWAP gate

Codercise I.13.3 — The Toffoli gate

Codercise I.13.4 — Mixed Controlled Gates

Codercise I.13.5 — The 3-controlled-NOT

Controlled-Z

The SWAP gate

The Toffoli gate

Codercise I.13.1 — The imposter $CZ$

Codercise I.13.5 — The $3$ -controlled-NOT