The three-inputTOFFOLI gate is the workhorse of circuit synthesis for classical log ic operations on quantum data, e.g., reversible arithmetic ci rcuits. In physical implementations, however,TOFFOLI gates are decomposed into six CNOT 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 CNOT-optimality. We study three-qubit circuits which contain less than six CNOT gates and implement a block-diagonal operator, then show that they implicitly d escribe the cosine-sine decomposition of a related operator. Leveraging the canonicity o f such decompositions to limit one-qubit gates appearing in respective circuits, we prove that then-qubit analogue of the TOFFOLI requires at least 2 n CNOT gates. Additionally, our results offer a complete classification of three-qubit diagonal operators by their CNOT-cost, which holds even if ancilla qubits are available. ∗Department of Mathematics, Princeton University, Princet on, NJ 08544. †Department of EECS, University of Michigan, Ann Arbor, MI 48 109.