We show that quantum-to-classical channels, i.e., quantum measurements, can be asymptotically simulated by an amount of classical communication equal to the quantum mutual information of the measurement, if sufficient shared randomness is available. This result generalizes Winter's measurement compression theorem for fixed independent and identically distributed inputs [Winter, CMP 244 (157), 2004] to arbitrary inputs, and more importantly, it identifies the quantum mutual information of a measurement as the information gained by performing it, independent of the input state on which it is performed. Our result is a generalization of the classical reverse Shannon theorem to quantum-to-classical channels. In this sense, it can be seen as a quantum reverse Shannon theorem for quantum-to-classical channels, but with the entanglement assistance and quantum communication replaced by shared randomness and classical communication, respectively. Our proof is based on quantum-proof randomness extractors and the post-selection technique for quantum channels [Christandl et al., PRL 102 (020504), 2009].
We show that quantum-to-classical channels, i.e., quantum measurements, can be asymptotically simulated by an amount of classical communication equal to the quantum mutual information of the measurement, if sufficient shared randomness is available. This result generalizes Winter's measurement compression theorem for fixed independent and identically distributed inputs [Winter, CMP 244 (157), 2004] to arbitrary inputs, and more importantly, it identifies the quantum mutual information of a measurement as the information gained by performing it, independent of the input state on which it is performed. Our result is a generalization of the classical reverse Shannon theorem to quantum-to-classical channels. In this sense, it can be seen as a quantum reverse Shannon theorem for quantum-to-classical channels, but with the entanglement assistance and quantum communication replaced by shared randomness and classical communication, respectively. Our proof is based on quantum-proof randomness extractors and the post-selection technique for quantum channels [Christandl et al., PRL 102 (020504), 2009].
We show that quantum-to-classical channels, i.e., quantum measurements, can be asymptotically simulated by an amount of classical communication equal to the quantum mutual information of the measurement, if sufficient shared randomness is available. This result generalizes Winter's measurement compression theorem for fixed independent and identically distributed inputs to arbitrary inputs, and more importantly, it identifies the quantum mutual information of a measurement as the information gained by performing it, independent of the input state on which it is performed. Our result is a generalization of the classical reverse Shannon theorem to quantum-to-classical channels. In this sense, it can be seen as a quantum reverse Shannon theorem for quantum-to-classical channels, but with the entanglement assistance and quantum communication replaced by shared randomness and classical communication, respectively. The proof is based on a novel one-shot state merging protocol for classically coherent states as well as the postselection technique for quantum channels, and it uses techniques developed for the quantum reverse Shannon theorem.
Winter's measurement compression theorem stands as one of the most penetrating insights of quantum information theory. In addition to making an original and profound statement about measurement in quantum theory, it also underlies several other general protocols used for entanglement distillation and local purity distillation. The theorem provides for an asymptotic decomposition of any quantum measurement into noise and information . This decomposition leads to an optimal protocol for having a sender simulate many independent instances of a quantum measurement and send the measurement outcomes to a receiver, using as little communication as possible. The protocol assumes that the parties have access to some amount of common randomness, which is a strictly weaker resource than classical communication. In this review, we provide a second look at Winter's measurement compression theorem, detailing the information processing task, giving examples for understanding it, reviewing Winter's achievability proof, and detailing a new approach to its single-letter converse theorem. We prove an extension of the theorem to the case in which the sender is not required to receive the outcomes of the simulated measurement. The total cost of common randomness and classical communication can be lower for such a 'non-feedback' simulation, and we prove a single-letter converse theorem demonstrating optimality. We then review the Devetak–Winter theorem on classical data compression with quantum side information, providing new proofs of its achievability and converse parts. From there, we outline a new protocol that we call 'measurement compression with quantum side information,' announced previously by two of us in our work on triple trade-offs in quantum Shannon theory. This protocol has several applications, including its part in the 'classically-assisted state redistribution' protocol, which is the most general protocol on the static side of the quantum information theory tree, and its role in reducing the classical communication cost in a task known as local purity distillation. We also outline a connection between measurement compression with quantum side information and recent work on entropic uncertainty relations in the presence of quantum memory. Finally, we prove a single-letter theorem characterizing measurement compression with quantum side information when the sender is not required to obtain the measurement outcome.
The Quantum Reverse Shannon Theorem states that any quantum channel can be simulated by an unlimited amount of shared entanglement and an amount of classical communication equal to the channel’s entanglement assisted classical capacity. In this paper, we provide a new proof of this theorem, which has previously been proved by Bennett, Devetak, Harrow, Shor, and Winter. Our proof has a clear structure being based on two recent information-theoretic results: one-shot Quantum State Merging and the Post-Selection Technique for quantum channels.
Dual to the usual noisy channel coding problem, where a noisy (classical or quantum) channel is used to simulate a noiseless one, reverse Shannon theorems concern the use of noiseless channels to simulate noisy ones, and more generally the use of one noisy channel to simulate another. For channels of nonzero capacity, this simulation is always possible, but for it to be efficient, auxiliary resources of the proper kind and amount are generally required. In the classical case, shared randomness between sender and receiver is a sufficient auxiliary resource, regardless of the nature of the source, but in the quantum case the requisite auxiliary resources for efficient simulation depend on both the channel being simulated, and the source from which the channel inputs are coming. For tensor power sources (the quantum generalization of classical IID sources), entanglement in the form of standard ebits (maximally entangled pairs of qubits) is sufficient, but for general sources, which may be arbitrarily correlated or entangled across channel inputs, additional resources, such as entanglement-embezzling states or backward communication, are generally needed. Combining existing and new results, we establish the amounts of communication and auxiliary resources needed in both the classical and quantum cases, the tradeoffs among them, and the loss of simulation efficiency when auxiliary resources are absent or insufficient. In particular we find a new single-letter expression for the excess forward communication cost of coherent feedback simulations of quantum channels (i.e. simulations in which the sender retains what would escape into the environment in an ordinary simulation), on non-tensor-power sources in the presence of unlimited ebits but no other auxiliary resource. Our results on tensor power sources establish a strong converse to the entanglement-assisted capacity theorem.
Quantum theory is, in some sense, “non-classical.” For instance, the behavior of entangled systems (i.e., shared quantum information) under measurements cannot, in general, be explained by shared classical information. With classical communication, on the other hand, both the correlations entanglement leads to as well as quantum channels can be reproduced in principle. Here, crucial questions are whether the required communications is finite; if so, then its exact amount is related to the “degree of non-classicality” of the quantum primitive. We apply information-theoretic results such as the reverse Shannon theorem for determining the required communication in the asymptotic limit. The communication complexity of a quantum channel is the minimal amount of classical communication required for classically simulating the process of preparation, transmission through the channel, and subsequent measurement of a quantum state. At present, only little is known about this quantity. Our generic procedure allows for systematically evaluating the communication complexity of channels in any general probabilistic theory, in particular quantum theory. The procedure is constructive and provides the most efficient classical protocols. We illustrate it by evaluating the communication complexity of sending single qubits over a noiseless quantum channel with some finite sets of quantum states and measurements. As a second application, we determine the classical-communication rate required for the simulation of the behavior under measurements of entangled states. Here, the communication cost can be directly interpreted as the “non-classicality” of the correlation. A particular example is the simulation of non-maximally entangled pure qubit pairs, where we find the required communication rate to behave monotonically with the strength of the entanglement. For different measures of non-locality, such as the number of required non-local (PR) boxes, another behavior had been reported for the single-shot scenario.
The entanglement-assisted classical capacity of a noisy quantum channel (C/sub E/) is the amount of information per channel use that can be sent over the channel in the limit of many uses of the channel, assuming that the sender and receiver have access to the resource of shared quantum entanglement, which may be used up by the communication protocol. We show that the capacity C/sub E/ is given by an expression parallel to that for the capacity of a purely classical channel: i.e., the maximum, over channel inputs /spl rho/, of the entropy of the channel input plus the entropy of the channel output minus their joint entropy, the latter being defined as the entropy of an entangled purification of /spl rho/ after half of it has passed through the channel. We calculate entanglement-assisted capacities for two interesting quantum channels, the qubit amplitude damping channel and the bosonic channel with amplification/attenuation and Gaussian noise. We discuss how many independent parameters are required to completely characterize the asymptotic behavior of a general quantum channel, alone or in the presence of ancillary resources such as prior entanglement. In the classical analog of entanglement-assisted communication - communication over a discrete memoryless channel (DMC) between parties who share prior random information - we show that one parameter is sufficient, i.e., that in the presence of prior shared random information, all DMCs of equal capacity can simulate one another with unit asymptotic efficiency.