Arbitrary two-qubit computation in 23 elementary gates

We address the problem of constructing quantum circuits to implement an arbitrary two-qubit quantum computation. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 controlled-NOT (CNOT) gates. We also constructively prove a worst-case upper bound of 23 elementary gates, of which at most four (CNOT gates) entail multiqubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of 61 gates, of which 18 may be CNOT gates.