  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.
