  The controlled-not gate and the single qubit gates are considered elementary
gates in quantum computing. It is natural to ask how many such elementary gates
are needed to implement more elaborate gates or circuits. Recall that a
controlled-U gate can be realized with two controlled-not gates and four single
qubit gates. We prove that this implementation is optimal if and only if the
matrix U satisfies the conditions tr U != 0, tr UX != 0, and det U != 1. We
also derive optimal implementations in the non-generic cases.

Quantum Physics