The two-party communication complexity model formalizes the study of
costs involved in distributed computation. Here, two processors
aim to jointly solve a task by communicating over a connecting link.
In a realistic setting, this link may be subject to noise and we may
wonder how reliably we can compute over this link, and what the
associated overhead is. An application of the Shannon noisy coding
theorem results in a simulation of protocols that is robust against
noise, but comes with a logarithmic factor overhead in communication
cost. In the 90's, Schulman gave an elegant simulation of interactive
protocols that incurs only _constant_ factor overhead, in spite of the
fact that we do not have the advantage of long block size for such
coding.

In this work, we consider the problem of coding for interactive
protocols with quantum communication. In this setting, the Schulman
scheme breaks down for a number of reasons. First, we do not know of a
quantum analogue of the ``tree codes'' used in the scheme.
Second, the scheme relies on re-computation of messages that are
corrupted beyond repair, which is not possible for quantum states
(by the ``no-cloning theorem'').

We describe a simulation of quantum communication protocols which
overcomes these hurdles while introducing only a constant factor
slowdown.

(Joint work with Falk Unger, UC Berkeley)