We consider the decomposition of arbitrary isometries into a sequence of single-qubit and controlled-not (cnot) gates. In many experimental architectures, the cnot gate is relatively costly and hence we aim to keep the number of these as low as possible. We derive a theoretical lower bound on the number of cnot 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 2 in the leading order. We also perform some further optimizations for certain cases where $m$ and $n$ are small. In addition, we show how to apply our result for isometries to give a decomposition scheme for an arbitrary quantum operation via Stinespring's theorem and derive a lower bound on the number of cnot gates in this case too. These results will have an impact on experimental efforts to build a quantum computer, enabling them to go further with the same resources.

• Received 3 June 2015
• Revised 11 November 2015

DOI:https://doi.org/10.1103/PhysRevA.93.032318