  Instantaneous nonlocal quantum computation refers to a process in which
spacelike separated parties simulate a nonlocal quantum operation on their
joint systems through the consumption of pre-shared entanglement. To prevent a
violation of causality, this simulation succeeds up to local errors that can
only be corrected after the parties communicate classically with one another.
However, this communication is non-interactive, and it involves just the
broadcasting of local measurement outcomes. We refer to this operational
paradigm as local operations and broadcast communication (LOBC) to distinguish
it from the standard local operations and (interactive) classical communication
(LOCC). In this paper, we show that an arbitrary two-qubit gate can be
implemented by LOBC with $\epsilon$-error using $O(\log(1/\epsilon))$ entangled
bits (ebits). This offers an exponential improvement over the best known
two-qubit protocols, whose ebit costs behave as $O(1/\epsilon)$. We also
consider the family of binary controlled gates on dimensions $d_A\otimes d_B$.
We find that any hermitian gate of this form can be implemented by LOBC using a
single shared ebit. In sharp contrast, a lower bound of $\log d_B$ ebits is
shown in the case of generic (i.e. non-hermitian) gates from this family, even
when $d_A=2$. This demonstrates an unbounded gap between the entanglement costs
of LOCC and LOBC gate implementation. Whereas previous lower bounds on the
entanglement cost for instantaneous nonlocal computation restrict the minimum
dimension of the needed entanglement, we bound its entanglement entropy. To our
knowledge this is the first such lower bound of its kind.
