Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.
Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.
A central question in classical information theory is that of source compression, which is the task where Alice receives a sample from a known probability distribution and needs to transmit it to the receiver Bob with small error. This problem has a one-shot solution due to Huffman, in which the messages are of variable length and the expected length of the messages matches the asymptotic and i.i.d. compression rate of the Shannon entropy of the source. In this work, we consider a quantum extension of above task, where Alice receives a sample from a known probability distribution and needs to transmit a part of a pure quantum state (that is associated to the sample) to Bob. We allow entanglement assistance in the protocol, so that the communication is possible through classical messages, for example using quantum teleportation. The classical messages can have a variable length and the goal is to minimize their expected length. We provide a characterization of the expected communication cost of this task, by giving a lower bound that is near optimal up to some additive factors. A special case of above task, and the quantum analogue of the source compression problem, is when Alice needs to transmit the whole of her pure quantum state. Here we show that there is no one-shot interactive scheme which matches the asymptotic and i.i.d. compression rate of the von Neumann entropy of the average quantum state. This is a relatively rare case in quantum information theory where the cost of a quantum task is significantly different from its classical analogue. Further, we also exhibit similar results for the fully quantum task of quantum state redistribution, employing some different techniques. We show implications for the one-shot version of the problem of quantum channel simulation.
A central question in the classical information theory is that of source compression, which is the task where Alice receives a sample from a known probability distribution and needs to transmit it to the receiver Bob with small error. This problem has a one-shot solution due to Huffman, in which the messages are of variable length and the expected length of the messages matches the asymptotic and independent identically distributed (i.i.d.) compression rate of the Shannon entropy of the source. In this paper, we consider a quantum extension of above task, where Alice receives a sample from a known probability distribution and needs to transmit a part of a pure quantum state (that is associated with the sample) to Bob. We allow entanglement assistance in the protocol, so that the communication is possible through classical messages, for example using quantum teleportation. The classical messages can have a variable length, and the goal is to minimize their expected length. We provide a characterization of the expected communication cost of this task, by giving a lower bound that is near optimal up to some additive factors. A special case of above task, and the quantum analogue of the source compression problem, is when Alice needs to transmit the whole of her pure quantum state. Here, we show that there is no one-shot interactive scheme which matches the asymptotic and i.i.d. compression rate of the von Neumann entropy of the average quantum state. This is a relatively rare case in the quantum information theory where the cost of a quantum task is significantly different from its classical analogue. Furthermore, we also exhibit similar results for the fully quantum task of quantum state redistribution, employing some different techniques. We show implications for the one-shot version of the problem of quantum channel simulation.
One of the fundamental tasks in classical information theory is the compression of information. Given access to many uses of a noiseless classical channel, what is the best that a sender and receiver can make of this resource for compressed data transmission? Shannon's compression theorem demonstrates that the Shannon entropy is the fundamental limit for the compression rate in the IID setting (recall the development in Section 13.4). That is, if one compresses at a rate above the Shannon entropy, then it is possible to recover the compressed data perfectly in the asymptotic limit, and otherwise, it is not possible to do so. This theorem establishes the prominent role of the entropy in Shannon's theory of information. In the quantum world, it very well could be that one day a sender and a receiver would have many uses of a noiseless quantum channel available, and the sender could use this resource to transmit compressed quantum information. But what exactly does this mean in the quantum setting? A simple model of a quantum information source is an ensemble of quantum states { pX(x) , ∣ψ x ⟩}, i.e., the source outputs the state ∣ψ x ⟩ with probability pX(x) , and the states {∣ψ x ⟩} do not necessarily have to form an orthonormal basis. Let us suppose for the moment that the classical data x is available as well, even though this might not necessarily be the case in practice. A naive strategy for compressing this quantum information source would be to ignore the quantum states coming out, handle the classical data instead, and exploit Shannon's compression protocol from Section 13.4.
The entanglement cost of a quantum channel is the minimal rate at which entanglement (between sender and receiver) is needed in order to simulate many copies of a quantum channel in the presence of free classical communication. In this paper, we show how to express this quantity as a regularized optimization of the entanglement formation over states that can be generated between sender and receiver. Our formula is the channel analog of a well-known formula for the entanglement cost of quantum states in terms of the entanglement of formation and shares a similar relation to the recently shattered hope for additivity. The entanglement cost of a quantum channel can be seen as the analog of the quantum reverse Shannon theorem in the case where free classical communication is allowed. The techniques used in the proof of our result are then also inspired by a recent proof of the quantum reverse Shannon theorem and feature the one-shot formalism for quantum information theory, the postselection technique for quantum channels as well as Sion's minimax theorem. We discuss two applications of our result. First, we are able to link the security in the noisy-storage model to a problem of sending quantum rather than classical information through the adversary's storage device. This not only improves the range of parameters where security can be shown, but also allows us to prove security for storage devices for which no results were known before. Second, our result has consequences for the study of the strong converse quantum capacity. Here, we show that any coding scheme that sends quantum information through a quantum channel at a rate larger than the entanglement cost of the channel has an exponentially small fidelity.
We study a problem from zero-error information theory—a topic well-known for its rich connections to combinatorics [1,8,10–12,14]—in a setting where a sender and receiver may use quantum entanglement, one of the most striking features of quantum mechanics. The problem that we consider is the classical source-channel coding problem , where Alice and Bob are each given an input from a random source and get access to a noisy channel through which Alice can send messages to Bob. Their goal is to minimize the average number of channel uses per source input while allowing Bob to learn Alice’s inputs. Here we show that entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes. We also consider the source problem , the case where Alice can send messages to Bob without noise. We prove a lower bound on the rate of source codes with entanglement in terms of a variant of the Lovász theta number [10,13], a graph parameter given by a semidefinite program.
After K. Bostro/spl uml/m and T. Felbinger observed that lossless quantum data compression does not exist unless decoders know the lengths of codewords, they introduced a classical noiseless channel to inform the decoder of a quantum source about the lengths of codewords. In this paper we analyze their codes and present: 1) a sufficient and necessary condition for the existence of such codes for given lists of lengths of codes; 2) a characterization of the optimal compression rate for their codes. However our main contribution is a more efficient way to use the classical channel. We propose a more general coding scheme. It turned out that the optimal compression can always be achieved by a code obtained by this scheme. A von Neumann entropy lower bound to rates of our codes and a necessary and sufficient condition to achieve the bound are obtained. The gap between this lower bound and the compression rates is also well analyzed. For a special family of quantum sources we provide a sharper lower bound in terms of Shannon entropy. Finally, we propose some problems for further research.