  We analyze implementations of bipartite unitaries by means of local
operations and classical communication (LOCC) assisted by shared entanglement.
We employ concepts and techniques developed in quantum Shannon theory to study
an asymptotic scenario, in which two distant parties perform the same bipartite
unitary on infinitely many pairs of inputs. We analyze minimum cost of
entanglement and classical communication per copy. For two-round LOCC
protocols, we derive a single-letter formula for the minimum cost of
entanglement and classical communication, under an additional requirement that
the error converges to zero faster than $1/n^4$, where $n$ is the number of
input pairs. The formula is given by the "Markovianizing cost" of a tripartite
state associated with the unitary, which can be computed by a finite-step
algorithm. We also derive a lower bound on the minimum cost of resources, which
applies for protocols with arbitrary number of rounds.
