We show how a non-local quantum controlled-NOT (CNOT) gate with multiple targets can be implemented with unit fidelity and unit probability. The explicit quantum circuit for implementing the operation is presented. Two schemes for probabilistic implementing the operation via partially entangled quantum channels with unit fidelity are put forward. The overall physical resources required for accomplishing these schemes are different, and the successful implementation probabilities are also different.