The goal of the covering lemma is perhaps opposite to that of the packing lemma because it applies to a setting in which one party wishes to make messages indistinguishable to another party (instead of trying to make them distinguishable, as in the packing lemma of the previous chapter). That is, the covering lemma is helpful when one party is trying to simulate a noisy channel to another party, rather than trying to simulate a noiseless channel. One party can accomplish this task by randomly “covering” the Hilbert space of the other party (this viewpoint gives the covering lemma its name). One can certainly simulate noise by choosing a quantum state uniformly at random from a large set of quantum states and passing along the chosen quantum state to a third party without indicating which state was chosen. But the problem with this approach is that it could potentially be expensive if the set from which we choose a random state is large, and we would really like to use as few resources as possible in order to simulate noise. That is, we would like the set from which we choose a quantum state uniformly at random to be as small as possible when simulating noise. The covering lemma is similar to the packing lemma in the sense that its conditions for application are general (involving bounds on projectors and an ensemble), and it gives an effective scheme for simulating noise when we apply it in an i.i.d. setting. One application of the covering lemma in quantum Shannon theory is in the construction of a code for transmitting private classical information over a quantum channel (discussed in Chapter 23). The method of proof for private classical transmission involves a clever combination of packing messages so that Bob can distinguish them, while covering Eve's space in such a way that Eve cannot distinguish the messages intended for Bob. A few other applications of the covering lemma are in secret key distillation, determining the amount of noise needed to destroy correlations in a bipartite state, and compressing the outcomes of an i.i.d. measurement on an i.i.d. quantum state.
The goal of the covering lemma is perhaps opposite to that of the packing lemma because it applies to a setting in which one party wishes to make messages indistinguishable to another party (instead of trying to make them distinguishable, as in the packing lemma of the previous chapter). That is, the covering lemma is helpful when one party is trying to simulate a noisy channel to another party, rather than trying to simulate a noiseless channel. One party can accomplish this task by randomly “covering” the Hilbert space of the other party (this viewpoint gives the covering lemma its name). One can certainly simulate noise by choosing a quantum state uniformly at random from a large set of quantum states and passing along the chosen quantum state to a third party without indicating which state was chosen. But the problem with this approach is that it could potentially be expensive if the set from which we choose a random state is large, and we would really like to use as few resources as possible in order to simulate noise. That is, we would like the set from which we choose a quantum state uniformly at random to be as small as possible when simulating noise. The covering lemma is similar to the packing lemma in the sense that its conditions for application are general (involving bounds on projectors and an ensemble), and it gives an effective scheme for simulating noise when we apply it in an i.i.d. setting. One application of the covering lemma in quantum Shannon theory is in the construction of a code for transmitting private classical information over a quantum channel (discussed in Chapter 23). The method of proof for private classical transmission involves a clever combination of packing messages so that Bob can distinguish them, while covering Eve's space in such a way that Eve cannot distinguish the messages intended for Bob. A few other applications of the covering lemma are in secret key distillation, determining the amount of noise needed to destroy correlations in a bipartite state, and compressing the outcomes of an i.i.d. measurement on an i.i.d. quantum state.
The goal of the covering lemma is perhaps opposite to that of the packing lemma because it applies in a setting where one party wishes to make messages indistinguishable to another party (instead of trying to make them distinguishable as in the packing lemma of the previous chapter). That is, the covering lemma is helpful when one party is trying to simulate a noisy channel to another party, rather than trying to simulate a noiseless channel. One party can accomplish this task by randomly covering the Hilbert space of the other party (this viewpoint gives the covering lemma its name). One can certainly simulate noise by choosing a quantum state uniformly at random from a large set of quantum states and passing along the chosen quantum state to a third party without telling which state was chosen. But the problem with this approach is that it could potentially be expensive if the set from which we choose a random state is large, and we would really like to use as few resources as possible in order to simulate noise. That is, we would like the set from which we choose a quantum state uniformly at random to be as small as possible when simulating noise. The covering lemma is similar to the packing lemma in the sense that its conditions for application are general (involving bounds on projectors and an ensemble), but it gives an asymptotically efficient scheme for simulating noise when we apply it in an IID setting.
The packing lemma is a general method for one party to “pack” or encode classical messages into a Hilbert space so that another party can distinguish the encoded messages. The first party can prepare an ensemble of quantum states, and the other party has access to a set of projectors using which he can form a quantum measurement. If the ensemble and the projectors satisfy the conditions of the packing lemma, then it guarantees the existence of a scheme by which the second party can distinguish the classical messages that the first party prepares. The statement of the packing lemma is quite general, and this approach has a great advantage because we can use it as a primitive for many coding theorems. Examples of coding theorems that we can prove using the packing lemma are the Holevo–Schumacher–Westmoreland (HSW) theorem for the transmission of classical information over a quantum channel and the entanglement-assisted classical capacity theorem for the transmission of classical information over an entanglement-assisted quantum channel (furthermore, Chapter 22 shows that these two protocols are sufficient to generate most known protocols in quantum Shannon theory). Combined with the covering lemma of the next chapter, the packing lemma gives a method for transmitting private classical information over a quantum channel, and this technique in turn gives a way to communicate quantum information over a quantum channel. As long as we can determine an ensemble and a set of projectors satisfying the conditions of the packing lemma, we can apply it in a straightforward way. For example, we prove the HSW coding theorem in Chapter 20 largely by relying on the properties of typical and conditionally typical subspaces that we proved in the previous chapter, and some of these properties are equivalent to the conditions of the packing lemma. The packing lemma is a “one-shot” lemma because it applies to a general scenario that is not limited only to i.i.d. uses of a quantum channel. This “oneshot” approach is part of the reason that we can apply it to a variety of situations. The technique of proving a “one-shot” result and applying it to the i.i.d.
The packing lemma is a general method for one party to pack classical messages into a Hilbert space so that another party can distinguish the packed messages. The first party can prepare an ensemble of quantum states, and the other party has access to a set of projectors from which he can form a quantum measurement. If the ensemble and the projectors satisfy the conditions of the packing lemma, then it guarantees the existence of a scheme by which the second party can distinguish the classical messages that the first party prepares. The statement of the packing lemma is quite general, and this approach has a great advantage because we can use it as a primitive in many coding theorems in quantum Shannon theory. Examples of coding theorems that we can prove with the packing lemma are the Holevo–Schumacher–Westmoreland (HSW) theorem for transmission of classical information over a quantum channel and the entanglement-assisted classical capacity theorem for the transmission of classical information over an entanglement-assisted quantum channel (furthermore, Chapter 21 shows that these two protocols are sufficient to generate most known protocols in quantum Shannon theory). Combined with the covering lemma of the next chapter, the packing lemma gives a method for transmitting private classical information over a quantum channel, and this technique in turn gives a way to communicate quantum information over a quantum channel.
We have now seen in Chapters 20–22 how Alice can communicate classical or quantum information to Bob, perhaps even with the help of shared entanglement. One might argue that these communication tasks are the most fundamental tasks in quantum Shannon theory, given that they have furthered our understanding of the nature of information transmission over quantum channels. However, when discussing the communication of classical information, we made no stipulation as to whether this classical information should be public, so that any third party might have partial or full access to it, or private, so that no third party has access. This chapter establishes the private classical capacity theorem, which gives the maximum rate at which Alice can communicate classical information privately to Bob without anyone else in the universe knowing what she sent to him. A variation of the information-processing task corresponding to this theorem was one of the earliest studied in quantum information theory, with the Bennett– Brassard-84 quantum key distribution protocol being the first proposed protocol for exploiting quantum mechanics to establish a shared secret key between two parties. The private classical capacity theorem is important for quantum key distribution because it establishes the maximum rate at which two parties can generate a shared secret key. Another equally important, but less obvious utility of private classical communication is in establishing a protocol for quantum communication at the coherent information rate. Section 22.2 demonstrated a somewhat roundabout way of arriving at the conclusion that it is possible to communicate quantum information reliably at the coherent information rate—recall that we “coherified” the entanglement-assisted classical capacity theorem and then exploited the coherent communication identity and catalytic use of entanglement. Establishing achievability of the coherent information rate via private classical coding is another way of arriving at the same result, with the added benefit that the resulting protocol does not require the catalytic use of entanglement. The intuition for quantum communication via privacy arises from the nocloning theorem. Suppose that Alice is able to communicate private classical messages to Bob, so that the channel's environment (Eve) is not able to distinguish which message Alice is transmitting to Bob.
The quantum capacity theorem is one of the most important theorems in quantum Shannon theory. It is a fundamentally “quantum” theorem in that it demonstrates that a fundamentally quantum information quantity, the coherent information, is an achievable rate for quantum communication over a quantum channel. The fact that the coherent information does not have a strong analog in classical Shannon theory truly separates the quantum and classical theories of information. The no-cloning theorem (Section 3.5.4) provides the intuition behind the quantum capacity theorem. The goal of any quantum communication protocol is for Alice to establish quantum correlations with the receiver Bob. We know well now that every quantum channel has an isometric extension, so that we can think of another receiver, the environment Eve, who is at a second output port of a larger unitary evolution. Were Eve able to learn anything about the quantum information that Alice is attempting to transmit to Bob, then Bob could not be retrieving this information—otherwise, they would violate the no-cloning theorem. Thus, Alice should figure out some subspace of the channel input where she can place her quantum information such that only Bob has access to it, while Eve does not. That the dimensionality of this subspace is exponential in the coherent information is perhaps then unsurprising in light of the above no-cloning reasoning. The coherent information is an entropy difference H ( B ) -H ( E )—a measure of the amount of quantum correlations that Alice can establish with Bob less the amount that Eve can gain. We proved achievability of the coherent information for quantum data transmission in Corollary 22.2.1, but the roundabout path that we followed to prove achievability there perhaps does not give much insight into the structure of a quantum code that achieves the coherent information. Our approach in this chapter is different and should shed more light on this structure. Specifically, we show how to make coherent versions of the private classical codes from the previous chapter.
In Chapter 3, we considered the transmission of information over a noisy broadcast channel subject to reliability and security constraints; we showed that appropriate coding schemes can exploit the presence of noise to confuse the eavesdropper and guarantee some amount of information-theoretic security. It is important to note that the wiretap channel model assumes that all communications occur over the channel, hence communications are inherently rate-limited and one-way. Consequently, the results obtained do not fully capture the role of noise for secrecy; in particular, for situations in which the secrecy capacity is zero, it is not entirely clear whether this stems from the lack of any “physical advantage” over the eavesdropper or the restrictions imposed on the communication schemes. The objective of this chapter is to study more precisely the fundamental role of noise in information-theoretic security. Instead of studying how we can communicate messages securely over a noisy channel, we now analyze how much secrecy we can extract from the noise itself in the form of a secret key. Specifically, we assume that the legitimate parties and the eavesdropper observe the realizations of correlated random variables and that the legitimate parties attempt to agree on a secret key unknown to the eavesdropper. To isolate the role played by noise, we remove restrictions on communication schemes and we assume that the legitimate parties can distill their key by communicating over a two-way, public, noiseless , and authenticated channel at no cost.