  We study and solve the problem of classical channel simulation with quantum
side information at the receiver. This is a generalization of both the
classical reverse Shannon theorem, and the classical-quantum Slepian-Wolf
problem. The optimal noiseless communication rate is found to be reduced from
the mutual information between the channel input and output by the Holevo
information between the channel output and the quantum side information.
  Our main theorem has two important corollaries. The first is a quantum
generalization of the Wyner-Ziv problem: rate-distortion theory with quantum
side information. The second is an alternative proof of the trade-off between
classical communication and common randomness distilled from a quantum state.
  The fully quantum generalization of the problem considered is quantum state
redistribution. Here the sender and receiver share a mixed quantum state and
the sender wants to transfer part of her state to the receiver using
entanglement and quantum communication. We present outer and inner bounds on
the achievable rate pairs.
