On the Entanglement Cost of One-Shot Compression
share
We revisit the task of compressing an ensemble of quantum states in the one-shot setting. The protocols achieving the best compression use shared entanglement that may be much larger than the original message, while others (with potentially larger communication cost) have entanglement cost bounded by the message length. This motivates the question as to whether entanglement is truly necessary for compression, and if so, how much of it is needed. Motivated by questions in communication complexity, we lift certain restrictions imposed on compression protocols in tasks such as state-splitting and channel simulation. We show that an ensemble constructed by Jain, Radhakrishnan, and Sen (ICALP'03) saturates the known bounds on the sum of communication and entanglement costs, even with the relaxed compression protocols we study. The ensemble and the associated one-way communication protocol have several remarkable properties. The ensemble is incompressible by more than a constant number of qubits without entanglement, even when constant error is allowed. Moreover, in the presence of entanglement, the communication cost of compression can be arbitrarily smaller than the entanglement cost. The quantum information cost of the protocol can thus be arbitrarily smaller than the cost of compression without entanglement. The ensemble can also be used to show the impossibility of reducing, via compression, the entanglement used in two-party protocols for computing Boolean functions.
READ FULL TEXT