We consider the decomposition of arbitrary isometries into a sequence of single-qubit and Controlled-NOT (C-NOT) gates. In many experimental architectures, the C-NOT gate is relatively expensive and hence we aim to keep the number of these as low as
possible. We derive a theoretical lower bound on the number of C-NOT gates required to decompose an arbitrary isometry from m to n qubits, and give three explicit gate decompositions that achieve this bound up to a factor of about two in the leading order. We also perform some bespoke optimizations for certain cases where m and n are small. In addition, we show how to apply our result for isometries to give decomposition schemes for arbitrary quantum operations and POVMs via Stinesprings theorem. These results will have an impact on experimental efforts to build a quantum computer, enabling them to go further with the same resources.
