How is a Toffoli gate built without using T gates?

Question

Can someone tell me how to make a Toffoli gate without using T gates? Can we use $R_x$ and $R_y$. If yes, then how?

I tried many circuits but I was unable to create the CCNOT gate out of $R_x$, $R_y$ and $R_z$.

Answer 1

The answer by Bertrand Einstein IV is the correct answer to the question as asked - if you only have single-qubit rotations and no entangling gate, you cannot create an entangling gate.

However, we can use the single qubit gates $R_X$ and $R_Y$ to create a $T$ gate and a Hadamard. These, combined with controlled-not give a standard construction for Toffoli. For example, the sequence $$ R_Y(-\pi/2)R_X(\pi/4)R_Y(\pi/2)=e^{i\pi/4}T $$ while $$ R_X(\pi)R_Y(\pi/2)=-i H. $$ Remember that global phases are irrelevant.

Answer 2

The $T$ gate as well as all possible single qubit rotations are non-entangling operations. That means if we have a circuit composed of single bit rotations, any non-entangled $n$-bit input, it will result in a $n$-bit non-entangled output.

The $CCNOT$ gate however is of course entangling, really all controlled gates are entangling, which means there exist non-entangled inputs to the gate which will result in entangled outputs. This is quite easy to show for the $CNOT$ and by extension the $CCNOT$.

You should now be able to deduce the answer to your question. The Toffoli Gate needs to be entangling, and rotations can never do that; hence we cannot build a Toffoli gate using the gate set proposed in the question.

Answer 3

$T$ gate is defined as $$ T= \begin{pmatrix} 1 & 0 \\ 0 & \mathrm{e}^{i\frac{\pi}{4}} \end{pmatrix}, $$ and $Rz(\theta)$ is $$ Rz(\theta)= \begin{pmatrix} \mathrm{e}^{-i\frac{\theta}{2}} & 0 \\ 0 & \mathrm{e}^{i\frac{\theta}{2}} \end{pmatrix} $$ If we factor out $\mathrm{e}^{-i\frac{\theta}{2}}$ we get $$ \mathrm{e}^{-i\frac{\theta}{2}} \begin{pmatrix} 1 & 0 \\ 0 & \mathrm{e}^{i\theta} \end{pmatrix}. $$ So, setting $\theta = \pi/4$ we get $T$ gate up to a global phase. This means that with $Rz$ gate we can implement $T$. Note that set of $Rx$, $Ry$ and $Rz$ gates is universal for single-qubit gates, i.e. it allows to costruct any single-qubit gate including $T$ gate.

To construct Toffoli gate we also need CNOT gate. CNOT together with the rotations above allows to implement any unitary operation on a quantum computer.

Answer 4

You can decompose the T gates themselves to create a Toffoli Gate. Here is one way of doing this:-

You can refer to this Qiskit chapter if you are interested and want to understand gate decomposition: https://qiskit.org/textbook/ch-gates/more-circuit-identities.html