Can someone help me understand the correlation between the 2 diagrams in the qiskit textbook. enter image description here


1 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}$: Controlled version of V gate from three rotations 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: Decomposition of the controlled-SX gate 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}}$: Decomposition of the controlled-SX gate using CNOT gates

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)$: Non-optimized Toffoli circuit We see that some of these gates cancel out, leaving us with the following circuit: Toffoli first optimization Furthermore, we can transform the 3-CNOTs structure into a 2-CNOTs structure like this: enter image description here 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.

  • 1
    $\begingroup$ In the decomposed diagram above there are 2 Z gates which means there should be 4 square root Z gates and each square root Z would need 2 CNOTS then it makes a total of 4*2 +2 =10 CNOT. Please explain how it becomes 8. Also what are the values of A,B and C in the diagram. $\endgroup$ Commented Jul 5, 2021 at 4:05
  • 1
    $\begingroup$ @AbhishekKishore A controlled-$\mathbf{Z}$ gate can be implemented using only one CNOT gate, as explained in the textbook (you just have to surround the CNOT with two $\mathbf{H}$ gates). I've edited my answer to add the expressions for $\mathbf{A}$, $\mathbf{B}$, $\mathbf{C}$ and $\alpha$. Please tell me if there is still something you don't understand. $\endgroup$
    – Tristan Nemoz
    Commented Jul 5, 2021 at 14:51
  • 1
    $\begingroup$ Thanks for explaining in such great detail $\endgroup$ Commented Jul 5, 2021 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.