Recognizing small-circuit structure in two-qubit operators

This work proposes numerical tests which determine whether a two-qubit operator has an atypically simple quantum circuit. Specifically, we describe formulas, written in terms of matrix coefficients, characterizing operators implementable with exactly zero, one, or two controlled-NOT (CNOT) gates and all other gates being one-qubit gates. We give an algorithm for synthesizing two-qubit circuits with an optimal number of CNOT gates and illustrate it on operators appearing in quantum algorithms by Deutsch-Josza, Shor, and Grover. In another application, our explicit numerical tests allow timing a given Hamiltonian to compute a CNOT modulo one-qubit gate, when this is possible.