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\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 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.

Figure 1

A circuit construction for a Toffoli gate using four $T$ gates. (a) The Toffoli${}^{☆}$ circuit by Selinger [18] that is almost a Toffoli gate, with the difference being the controlled-$S^{†}$ operation. (b) Our circuit combines the Toffoli${}^{☆}$ circuit with a phase correction and teleportation to produce an exact Toffoli gate. The measurement is in the ${\sigma }^z$ basis, and the double vertical lines indicate that the controlled-${\sigma }^z$ correction is conditioned on the measurement result being $|1\rangle$.

Figure 2

An error-detecting Toffoli gate. The measurement is in the ${\sigma }^z$ basis, and obtaining result $|1\rangle$ indicates an error was detected, so the qubits should be discarded.

Figure 3

An error-detecting Toffoli gate. The red dashed lines indicate how any single ${\sigma }^z$ error will propagate to the readout qubit. The measurement is in the ${\sigma }^z$ basis, and obtaining result $|1\rangle$ indicates an error was detected, so the qubits should be discarded. As long as the ancilla qubits are initialized perfectly to $|0\rangle$ and the cnot and $H$ gates have no errors, then only ${\sigma }^z$ errors in the $T$ gates matter, as ${\sigma }^x$ errors cannot propagate to data qubits. If the probability of a ${\sigma }^z$ error in each $T$ gate is an independent, identically distributed (i.i.d.) Bernoulli$\left(p\right)$, then the success probability is $1-8p$ and the a posteriori error probability is $28p^2$, to lowest order in $p$.

Figure 4

Proper use of an error-detecting Toffoli ancilla. All measurements are in the ${\sigma }^z$ basis. The ancilla-production circuit in the box in the upper left corner is probabilistic. A measurement result of $|1\rangle$ indicates the circuit failed, in which case the qubits are discarded. Because the Toffoli ancilla is not coupled to any other part of the quantum computation, its production can be repeated until success. The subsequent cnot gates and measurements teleport data qubits through the Toffoli gate encoded in the ancilla (cf. p. 488 of Ref. [2]). Clifford-group gates are applied conditional on measurements showing outcome $|1\rangle$, as indicated by the parallel double lines.