The simplified Toffoli gate implementation by Margolus is optimal Academic Article uri icon


  • Unitary operations are expressed in the quantum circuit model as a finite sequence of elementary gates, such as controlled-not gates and single qubit gates. We prove that the simplified Toffoli gate by Margolus, which coincides with the Toffoli gate up to a single change of sign, cannot be realized with less than three controlled-not gates. If the circuit is implemented with three controlled-not gates, then at least four additional single qubit gates are necessary. This proves that the implementation suggested by Margolus is optimal.

author list (cited authors)

  • Song, G., & Klappenecker, A.

publication date

  • January 1, 2003 11:11 AM