Multi-qubit Toffoli with exponentially fewer T gates

David Gosset, Robin Kothari, Chenyi Zhang

Prior work of Beverland et al. has shown that any exact Clifford+$T$ implementation of the $n$-qubit Toffoli gate must use at least $n$ $T$ gates. Here we show how to get away with…