  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 Stinespring's theorem.
These results will have an impact on experimental efforts to build a quantum
computer, enabling them to go further with the same resources.
