In this addendum, I want to briefly talk about the Toffoli gate, named after Tommaso Toffoli, a BU professor. The Toffoli gate is also known as the CCNOT gate.
The CCNOT gate functionally does the same thing as the CNOT gate, but with two control qubits instead of just one. If both are $1$, then an $X$ gate is applied on the target qubit.
In matrix form, it is defined as
$$ CCX = \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 & 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{bmatrix}. $$Remember that the matrix is $8 \times 8$ since this is a circuit that acts on 3 qubits. Much like the CNOT gate, we can alternatively think of it as mapping $\{a, b, c\} \to \{a, b, c \oplus ab\}$.
I don't know if the Toffoli gate will explicitly come up in any future lessons, but I wanted to bring it up since it is classically universal. This means that given any boolean function $f(x_1,\dots,x_m)$, a combination of Toffoli gates can take the inputs $x_1,\dots,x_m$ and some extra bits (known as ancilla bits), you can produce $f(x_1,\dots,x_m)$. This usually often involves retaining the inputs as well as using some extra bits (known as garbage) that can be discarded.
Furthermore, in a quantum setting, it turns out that Toffoli gates and Hadamard gates alone are universal. Intuitively, you can think of the Toffoli gates as covering the classical operations and the Hadamard gates as covering the superpositions.
The last thing I want to bring up about the Toffoli gate is a few examples of well-known gates that we can produce with the Toffoli gate. Remember that $CCX(a, b, c) = \{a, b, c \oplus ab\}$.
Let's start with the NOT gate. We know that if both control bits are $1$, the target bit will always flip. Therefore, $\neg c = CCX(1, 1, c)$. Conversely, if the target bit is $0$, we know that $0 \oplus ab = a \land b$. Hence we get the AND gate, $a \land b = CCX(a, b, 0)$.
For the OR gate, we know that $a \lor b = \lnot (\lnot a \land \lnot b)$. So we just apply NOTs on $a$ and $b$ using a Toffoli where both control bits are $1$, and then apply an AND using a Toffoli where the target bit is $0$. We then apply another Toffoli as the final NOT.
For CNOT, we can just fix one of the control bits to be $1$, so $CX(a, b) = CCX(a, 1, b)$. This will also encode $a \oplus b$ in place of $b$, allowing us to create XOR as well.
Hopefully these few examples give you a sense of the versatility of the Toffoli gate. It will underpin a lot of the more complicated circuits we cover in later weeks, even if we don't explicitly talk about it!