What is the correlation between Toffoli and a more generic rotation shown in qiskit textbook

Question

Can someone help me understand the correlation between the 2 diagrams in the qiskit textbook.

Answer 1

The first diagram is a generic construction showing how it is possible to build a $\mathsf{CC}\mathbf{U}$ gate, which is the gate that applies $\mathbf{U}$ to the third qubit only if both first qubits are in state $|1\rangle$. It uses the controlled version of the $\mathbf{V}$ gate (and its inverse), which is a gate such that: $$\mathbf{V}^2=\mathbf{U}$$ You can quickly check that this circuit indeed works as intended:

1. If both first qubits are in state $|0\rangle$, no gate is applied, since they are all controlled by at least one of those qubits.
2. If the first one is in state $|0\rangle$ and the second one in state $|1\rangle$, we apply both $\mathsf{C}\mathbf{V}$ and $\mathsf{C}\mathbf{V}^\dagger$ on the third qubit, which cancel out.
3. If the first one is in state $|1\rangle$ and the second one in state $|0\rangle$, we apply both $\mathsf{C}\mathbf{V}^\dagger$ and $\mathsf{C}\mathbf{V}$ on the third qubit, which cancel out.
4. Finally, if both qubits are in state $|1\rangle$, we apply $\mathbf{V}$ twice in the third qubit, which is equivalent to applying $\mathbf{U}$ once on it, since $\mathbf{V}^2=\mathbf{U}$.

The Toffoli gate is essentially a $\mathsf{CC}\mathbf{X}$ gate. Hence, if we were able to implement the square root of $\mathbf{X}$ as a controlled gate, we would be able to use the technique depicted in the first diagram. We can then use the previous section of the textbook, which tells us that for an arbitray single-qubit gate $\mathbf{V}$: with $\mathbf{ABC}=\mathbf{I}$ and $\mathrm{e}^{\mathrm{i\alpha}}\mathbf{AZBZC}=\mathbf{V}$.For instance using this answer, we can define: $$\begin{align*}\mathbf{A} &= \mathbf{I}\\\mathbf{B}&=\mathbf{H}\,\mathbf{T}^{-1}\,\mathbf{H}\\\mathbf{C}&=\mathbf{H\,T\,H}\\\alpha&=\frac\pi4\end{align*}\,.$$

It is easy to see that $\mathbf{A\,B\,C}=\mathbf{I}$. Now let us compute $\mathrm{e}^{\mathrm{i}\,\frac\pi4}\,\mathbf{A\,Z\,B\,Z\,C}$. Using the fact that $\mathbf{H\,Z\,H}=\mathbf{X}$, we get:

$$\begin{align*} \mathrm{e}^{\mathrm{i}\,\frac\pi4}\,\mathbf{A\,Z\,B\,Z\,C} &= \mathrm{e}^{\mathrm{i}\,\frac\pi4}\,\mathbf{Z}\,\underbrace{\mathbf{H}\,\mathbf{T}^{-1}\,\mathbf{H}}_{\mathbf{B}}\,\mathbf{Z}\,\underbrace{\mathbf{H}\,\mathbf{T}\,\mathbf{H}}_{\mathbf{C}}\\ &=\mathrm{e}^{\mathrm{i}\,\frac\pi4}\,\mathbf{Z}\,\mathbf{H}\,\mathbf{T}^{-1}\,\mathbf{X}\,\mathbf{T}\,\mathbf{H}\\ &=\mathrm{e}^{\mathrm{i}\,\frac\pi4}\,\begin{pmatrix}1&0\\0&-1\end{pmatrix}\,\frac{1}{\sqrt{2}}\,\begin{pmatrix}1&1\\1&-1\end{pmatrix}\,\mathbf{T}^{-1}\,\mathbf{X}\,\mathbf{T}\,\mathbf{H}\\ &= \frac{\mathrm{e}^{\mathrm{i}\,\frac\pi4}}{\sqrt{2}}\,\begin{pmatrix}1&1\\-1&1\end{pmatrix}\,\begin{pmatrix}1&0\\0&\mathrm{e}^{-\mathrm{i}\,\frac\pi4}\end{pmatrix}\,\mathbf{X}\,\mathbf{T}\,\mathbf{H}\\ &=\frac{\mathrm{e}^{\mathrm{i}\,\frac\pi4}}{\sqrt{2}}\,\begin{pmatrix}1&\mathrm{e}^{-\mathrm{i}\,\frac\pi4}\\-1&\mathrm{e}^{-\mathrm{i}\,\frac\pi4}\end{pmatrix}\,\begin{pmatrix}0&1\\1&0\end{pmatrix}\,\mathbf{T}\,\mathbf{H}\\ &=\frac{\mathrm{e}^{\mathrm{i}\,\frac\pi4}}{\sqrt{2}}\,\begin{pmatrix}\mathrm{e}^{-\mathrm{i}\,\frac\pi4}&1\\\mathrm{e}^{-\mathrm{i}\,\frac\pi4}&-1\end{pmatrix}\,\begin{pmatrix}1&0\\0&\mathrm{e}^{\mathrm{i}\,\frac\pi4}\end{pmatrix}\,\mathbf{H}\\ &=\frac{\mathrm{e}^{\mathrm{i}\,\frac\pi4}}{\sqrt{2}}\,\begin{pmatrix}\mathrm{e}^{-\mathrm{i}\,\frac\pi4}&\mathrm{e}^{\mathrm{i}\,\frac\pi4}\\\mathrm{e}^{-\mathrm{i}\,\frac\pi4}&-\mathrm{e}^{\mathrm{i}\,\frac\pi4}\end{pmatrix}\,\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\\ &=\frac{\mathrm{e}^{\mathrm{i}\,\frac\pi4}}{2}\,\begin{pmatrix}2\,\cos\left(\frac\pi4\right)&-2\,\mathrm{i}\,\sin\left(\frac\pi4\right)\\-2\,\mathrm{i}\,\sin\left(\frac\pi4\right)&2\,\cos\left(\frac\pi4\right)\end{pmatrix}\\ &=\frac{\mathrm{e}^{\mathrm{i}\,\frac\pi4}}{\sqrt{2}}\,\begin{pmatrix}1&-\mathrm{i}\\-\mathrm{i}&1\end{pmatrix}\,. \end{align*}$$ This last expression corresponds to the expression of $\sqrt{\mathbf{X}}$. Thus, a valid circuit for implementing the controlled-$\sqrt{\mathbf{X}}$ gate is: As stated in the textbook, a $\mathsf{C}\mathbf{Z}$ gate can be expressed in terms of two $\mathbf{H}$ gates and one CNOT. Hence, the following circuit is equivalent for decomposing $\sqrt{\mathbf{X}}$:

Thus, we can finally construct a valid circuit for the Toffoli gate using the aforementioned technique. Note that $\mathbf{T}=\mathbf{U1}\left(\frac\pi4\right)$: We see that some of these gates cancel out, leaving us with the following circuit: Furthermore, we can transform the 3-CNOTs structure into a 2-CNOTs structure like this: It may be possible to optimize this further to only use 6 CNOTs gates, but that's not the point.

Since we want the number of CNOT gates to be as low as possible, this method isn't used to implement the Toffoli gate, since we happen to know the optimal decomposition, which is given on the second diagram.

The goal of the textbook is thus to show that while the method is generic and works for any gate, it does not ensure that the resulting circuit is optimal in terms of implementation. It may require post-processing as we did to optimize it, and there is no guarantee that you will be able to get the optimal circuit be performing such transformations. This may still be useful though, as we do not know the optimal decomposition for any controlled gate as far as I know. This is why, I guess, they put "It turns out that the minimum number of CNOT gates required to implement the Toffoli gate is six": to emphasize that the generic method they described just before doesn't necessarily yield the optimal result.