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$.
$\begingroup$ $\endgroup$
Add a comment |
4 Answers
$\begingroup$ $\endgroup$
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.
$\begingroup$ $\endgroup$
1 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.
- $\begingroup$ Thank you. But what gate set can we choose to reduce the gate complexity other than the actutal decompostion of the Toffoli gate using T gate. This question was asked in a seminar and they asked us to create the toffoli gate with or without T gate but the circuit should be different than actual decomposition. I tried but i am not able to reach to the solution. Can you please guide me in this. $\endgroup$Tarun Kumar– Tarun Kumar2021-09-25 07:13:16 +00:00Commented Sep 25, 2021 at 7:13
$\begingroup$ $\endgroup$
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.
- $\begingroup$ Thank you. But what gate set can we choose to reduce the gate complexity other than the actual decomposition of the Toffoli gate using T gate. This question was asked in a seminar and they asked us to create the toffoli gate with or without T gate but the circuit should be different than actual decomposition. I tried but i am not able to reach to the solution. Can you please guide me in this. $\endgroup$Tarun Kumar– Tarun Kumar2021-09-25 12:18:11 +00:00Commented Sep 25, 2021 at 12:18
- $\begingroup$ @MinhPham: Did you mean to react on my comment or Tarun Kumar's? If the second option is right, please start your comment with @ followed by name of the user you want to communicate with. $\endgroup$Martin Vesely– Martin Vesely2021-09-29 15:57:22 +00:00Commented Sep 29, 2021 at 15:57
- $\begingroup$ Well what is the "actual" decomposition you are referring to, because there are a few decompositions that I know off. @TarunKumar $\endgroup$Minh Pham– Minh Pham2021-09-29 17:03:48 +00:00Commented Sep 29, 2021 at 17:03
$\begingroup$ $\endgroup$
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
