Efficient decomposition of multi-qubit gates

Applications in the NISQ era are restricted by the coherence time of the qubits thereby restricting the depth of the quantum circuit. Additionally, every hardware platform has limitations on the available set of hardware native gates. We show how to efficiently decompose a multi-qubit gate into native two-qubit gates minimizing both the depth and the number of two-qubit gates. Given a computational model, we argue that the technique is optimal in terms of the number of hardware native gates and the overall depth of the decomposition. Starting from decompositions for 1-d and star Hardware graphs, we generalize the procedure to any generic Hardware graph and provide exact expressions for the depth and number of two-qubit gates of the circuit. Furthermore, we show how to efficiently combine the decomposition of multi-qubit gates for a few specific problems.