Optimal local implementation of nonlocal quantum gates - art. no. 052317

We investigate the minimal resources that are required in the local impleme ntation of nonlocal quantum gates in a distributed quantum computer. Both c lassical communication requirements and entanglement consumption are invest igated. We present general statements on the minimal resource requirements and present optimal procedures for a number of important gates, including c ontrolled-NOT (CNOT) and Toffoli gates. We show that one bit of classical c ommunication in each direction is both necessary and sufficient for the non local implementation of the quantum CNOT, while in general two bits in each direction is required for the implementation of a general two-bit quantum gate. In particular, the state swapper requires this maximum classical comm unication overhead. Extensions of these ideas to multiparty gates are prese nted.