  One of the most intriguing facts about communication using quantum states is
that these states cannot be used to transmit more classical bits than the
number of qubits used, yet there are ways of conveying information with
exponentially fewer qubits than possible classically. Moreover, these methods
have a very simple structure---they involve little interaction between the
communicating parties. We look more closely at the ways in which information
encoded in quantum states may be manipulated, and consider the question as to
whether every classical protocol may be transformed to a ``simpler'' quantum
protocol of similar efficiency. By a simpler protocol, we mean a protocol that
uses fewer message exchanges. We show that for any constant k, there is a
problem such that its k+1 message classical communication complexity is
exponentially smaller than its k message quantum communication complexity, thus
answering the above question in the negative. Our result builds on two
primitives, local transitions in bi-partite states (based on previous work) and
average encoding which may be of significance in other applications as well.
