An important result from the mid
nineties shows that any unitary
evolution may be realized as a sequence
of controlled-not and one-qubit gates.
This work surveys especially efficient
circuits in this library, in the special
case of evolutions on two-quantum bits.
In particular, we show that to construct
an arbitrary two-qubit state from
|00>, one CNOT gate suffices.
To simulate an arbitrary two-qubit operator up to relative phases,
two CNOTs suffice. To simulate an
arbitrary two-qubit operator up to
global phase, three CNOTs
suffice. In each case, we construct
an explicit circuit and prove optimality
in the generic case. We also contribute
a procedure to determine the minimal
number of CNOT gates necessary to simulate a given two-qubit operator up
to global phase. We use this procedure
to discuss timing a given Hamiltonian
to simulate the CNOT and to determine
an optimal circuit for the two-qubit Quantum Fourier Transform.
Our constructive proofs amount to
circuit synthesis algorithms and have
been coded in C++.