On the CNOT -cost of TOFFOLI gates

The three-input \ gate is the workhorse of circuit synthesis for classical logic operations on quantum data, e.g., reversible arithmetic circuits. In physical implementations, however, \ gates are decomposed into six \ gates and several one-qubit gates. Though this decomposition has been known for at least 10 years, we provide here the first demonstration of its -optimality. We study three-qubit circuits which contain less than six \ gates and implement a block-diagonal operator, then show that they implicitly describe the cosine-sine decomposition of a related operator. Leveraging the canonical nature of such decompositions to limit one-qubit gates appearing in respective circuits, we prove that the n-qubit analogue of the \ requires at least $2n$ \ gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their -cost, which holds even if ancilla qubits are available.