The information-theoretic costs of simulating quantum measurements

Abstract

Winter's measurement compression theorem stands as one of the most\npenetrating insights of quantum information theory (QIT). In addition to making\nan original and profound statement about measurement in quantum theory, it also\nunderlies several other general protocols in QIT. In this paper, we provide a\nfull review of Winter's measurement compression theorem, detailing the\ninformation processing task, giving examples for understanding it, reviewing\nWinter's achievability proof, and detailing a new approach to its single-letter\nconverse theorem. We prove an extension of the theorem to the case in which the\nsender is not required to receive the outcomes of the simulated measurement.\nThe total cost of common randomness and classical communication can be lower\nfor such a "non-feedback" simulation, and we prove a single-letter converse\ntheorem demonstrating optimality. We then review the Devetak-Winter theorem on\nclassical data compression with quantum side information, providing new proofs\nof its achievability and converse parts. From there, we outline a new protocol\nthat we call "measurement compression with quantum side information," announced\npreviously by two of us in our work on triple trade-offs in quantum Shannon\ntheory. This protocol has several applications, including its part in the\n"classically-assisted state redistribution" protocol, which is the most general\nprotocol on the static side of the quantum information theory tree, and its\nrole in reducing the classical communication cost in a task known as local\npurity distillation. We also outline a connection between measurement\ncompression with quantum side information and recent work on entropic\nuncertainty relations in the presence of quantum memory. Finally, we prove a\nsingle-letter theorem characterizing measurement compression with quantum side\ninformation when the sender is not required to obtain the measurement outcome.\n