  Quantum teleportation uses prior shared entanglement and classical
communication to send an unknown quantum state from one party to another.
Remote state preparation (RSP) is a similar distributed task in which the
sender knows the entire classical description of the state to be sent. (This
may also be viewed as the task of non-oblivious compression of a single sample
from an ensemble of quantum states.) We study the communication complexity of
approximate remote state preparation, in which the goal is to prepare an
approximation of the desired quantum state. Jain [Quant. Inf. & Comp., 2006]
showed that the worst-case communication complexity of approximate RSP can be
bounded from above in terms of the maximum possible information in an encoding.
He also showed that this quantity is a lower bound for communication complexity
of (exact) remote state preparation. In this work, we tightly characterize the
worst-case and average-case communication complexity of remote state
preparation in terms of non-asymptotic information-theoretic quantities. We
also show that the average-case communication complexity of RSP can be much
smaller than the worst-case one. In the process, we show that n bits cannot be
communicated with less than n transmitted bits in LOCC protocols. This
strengthens a result due to Nayak and Salzman [J. ACM, 2006] and may be of
independent interest.
