  We present two new constructions for the Toffoli gate which substantially
reduce resource costs in fault-tolerant quantum computing. The first
contribution is a Toffoli gate requiring Clifford operations plus only four $T
= \exp(i\pi\sigma^z/8)$ gates, whereas conventional circuits require seven $T$
gates. An extension of this result is that adding $n$ control inputs to a
controlled gate requires $4n$ $T$ gates, whereas the best prior result was
$8n$. The second contribution is a quantum circuit for the Toffoli gate which
can detect a single $\sigma^z$ error occurring with probability $p$ in any one
of eight $T$ gates required to produce the Toffoli. By post-selecting circuits
that did not detect an error, the posterior error probability is suppressed to
lowest order from $4p$ (or $7p$, without the first contribution) to $28p^2$ for
this enhanced construction. In fault-tolerant quantum computing, this
construction can reduce the overhead for producing logical Toffoli gates by an
order of magnitude.
