Minimal universal two-qubit controlled-NOT-based circuits

We give quantum circuits that simulate an arbitrary two-qubit unitary operator up to a global phase. For several quantum gate libraries we prove that gate counts are optimal in the worst and average cases. Our lower and upper bounds compare favorably to previously published results. Temporary storage is not used because it tends to be expensive in physical implementations. For each gate library, the best gate counts can be achieved by a single universal circuit. To compute the gate parameters in universal circuits, we use only closed-form algebraic expressions, and in particular do not rely on matrix exponentials. Our algorithm has been coded in C++.