Chenyi Zhang [Stanford]

Abstract: The Clifford + T gate set is the canonical instruction set in many fault-tolerant quantum computing architectures, in which T gates dominate the overall resource cost. In this work, we study the implementation of the n-qubit Toffoli gate—the quantum analogue of the n-bit AND function—within the Clifford + T circuit model. Prior work of Beverland et al. has shown that any exact implementation of the n-qubit Toffoli gate must use at least n T gates. Here we show how to get away with exponentially fewer T gates, at the cost of incurring a tiny 1/poly(n) error that can be neglected in most practical situations. More precisely, the n-qubit Toffoli gate can be implemented to within error ϵ in the diamond distance by a randomly chosen Clifford+T circuit with at most O(log(1/ϵ)) T gates. We also give a matching Ω(log(1/ϵ)) lower bound that establishes optimality, and we show that any purely unitary implementation achieving even constant error must use Ω(n) T gates. We also extend our sampling technique to implement other Boolean functions. Finally, we describe upper and lower bounds on the T-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue..