Efficient Implementation of Multi-Controlled Quantum Gates

We present an implementation of multi-controlled quantum gates which provides significant reductions of cost compared to state-of-the-art methods. The operator applied on the target qubit is a unitary, special unitary, or the Pauli X operator (Multi-Controlled Toffoli), and requires one clean ancilla, no ancilla, and one dirty ancilla, respectively. We generalize our methods for any number of target qubits, and provide further cost reductions if additional ancilla qubits are available. For each type of multi-controlled gate, we provide implementations for unrestricted (all-to-all) connectivity and for linear-nearest-neighbor. All of the methods use a linear cost of gates from the Clifford+T (fault-tolerant) set. In the context of linear-nearest-neighbor (LNN) architecture, the cost and depth of our circuits scale linearly irrespective of the position of the qubits on which the gate is applied. Our methods directly improve the compilation process of many quantum algorithms, providing optimized circuits. Given the scale of our improvements, for example, quadratic to linear CNOT count for LNN, they will naturally result in a large reduction of errors.