Optimal Conversion of Nonlocal Unitary Operations

We study when a nonlocal unitary operation acting on two $d$-level systems can probabilistically simulate another one when arbitrary local operations and classical communication are allowed. We provide necessary and sufficient conditions for the simulation to be possible. Probabilistic interconvertability is used to define an equivalence relation between gates. We show that this relation induces a finite number of classes that we identify. In the case of two qubits, two classes of nonlocal operations exist. We show how the representatives of these classes, CNOT and SWAP, can be deterministically converted into any operation of its class and calculate the optimal probability of the reverse process.