  Can quantum communication be more efficient than its classical counterpart?
Holevo's theorem rules out the possibility of communicating more than n bits of
classical information by the transmission of n quantum bits --- unless the two
parties are entangled, in which case twice as many classical bits can be
communicated but no more. In apparent contradiction, there are distributed
computational tasks for which quantum communication cannot be simulated
efficiently by classical means. In extreme cases, the effect of transmitting
quantum bits cannot be achieved classically short of transmitting an
exponentially larger number of bits.
  In a similar vein, can entanglement be used to save on classical
communication? It is well known that entanglement on its own is useless for the
transmission of information. Yet, there are distributed tasks that cannot be
accomplished at all in a classical world when communication is not allowed, but
that become possible if the non-communicating parties share prior entanglement.
This leads to the question of how expensive it is, in terms of classical
communication, to provide an exact simulation of the spooky power of
entanglement.
