  In order to demonstrate non-trivial quantum computations experimentally, such
as the synthesis of arbitrary entangled states, it will be useful to understand
how to decompose a desired quantum computation into the shortest possible
sequence of one-qubit and two-qubit gates. We contribute to this effort by
providing a method to construct an optimal quantum circuit for a general
two-qubit gate that requires at most 3 CNOT gates and 15 elementary one-qubit
gates. Moreover, if the desired two-qubit gate corresponds to a purely real
unitary transformation, we provide a construction that requires at most 2 CNOTs
and 12 one-qubit gates. We then prove that these constructions are optimal with
respect to the family of CNOT, y-rotation, z-rotation, and phase gates.
