  The simplest decomposition of a Toffoli gate acting on three qubits requires
{\em five} 2-qubit gates. If we restrict ourselves to controlled-sign (or
controlled-NOT) gates this number climbs to six. We show that the number of
controlled-sign gates required to implement a Toffoli gate can be reduced to
just {\em three} if one of the three quantum systems has a third state that is
accessible during the computation, i.e. is actually a qutrit. Such a
requirement is not unreasonable or even atypical since we often artificially
enforce a qubit structure on multilevel quantums systems (eg. atoms, photonic
polarization and spatial modes). We explore the implementation of these
techniques in optical quantum processing and show that linear optical circuits
could operate with much higher probabilities of success.
