Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

The Clifford + T gate set is the canonical model for 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 Clifford+T 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.