An arbitrary two-qubit computation in 23 elementary gates or less

Quantum circuits currently constitute a dominant model for quantum computation according to M. Nielsen and I. Chuang (2000). Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and a small number of elementary quantum gates by A. Barenco et al. (1995) and G. Song and A. Klappenecker (2003) as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worst-case upper bound to 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previous known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm according to G. Cybenko (2001) has a worst case of 61 gates of which 18 may be CNOTs. Our technique rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of two-qubit gate with respect to the "magic basis" of phase-shifted Bell states by N. Khaneja et al. (2001) and M. Lewenstein et al. (2001). We extend this decomposition in terms of elementary gates for quantum computation.