Let's say I have a circuit that given in the figure enter image description here

As we can see that this circuit consists of $2$-Toffoli gates and $4$ C-NOT gates, and to construct this entire circuit using only single qubit gates I would require at least $12$ C-NOT gates $6$ for each of the step UMA and MAJ. That makes it a total of at least $16$ C-NOT Gates. Now my question is if I modify these circuits by putting two controls for each of them such that each of them operates if both controls are (say) $1$. Then I have $2$ CCCC-NOT gates and $4$ CCC-NOT gates. Now for this, I need at least $(8\times 4 + 10\times 2=52)$ C-NOT gates.

This is using an article that says to stimulate a $n$ qubit Toffoli gate we need at least $2n$ C-NOT gates.

Is my reasoning for my circuit correct? Can somebody help?

  • 2
    $\begingroup$ You are not doing any simplifications. For example, see answer about automatic groups. $\endgroup$ – AHusain Jun 8 '19 at 21:35
  • $\begingroup$ Please clarify the question. You want to know the minimum number of CNOTs to simulate an $n$ qubit Toffoli? Or you want to rewrite your circuit using only CNOT? Or something else? $\endgroup$ – bRost03 Jun 10 '19 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.