Low-overhead constructions for the fault-tolerant Toffoli gate

We present two 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^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 ^z error occurring with probability p in any one of eight T gates required to produce the Toffoli gate. By postselecting 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.