Optimal realizations of simplified Toffoli gates
Guang Song, Andreas Klappenecker · Quantum Information and Computation · 2004
A simplified Toffoli gate coincides with the Toffoli gate except that the result is allowed to differ on one computational basis state by a phase factor. We prove that the simplified Toffoli gate implementation by Margolus is optimal, in the sense that it attains a lower bound of {\em three} controlled-not gates, and subject to that, a sharp lower bound of {\em four} single-qubit gates. We also discuss optimal implementations of other simplified Toffoli gates, and explain why the phase factor $-1$ invariably occurs in such implementations.