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 simplest quantum system is the physical quantum bit or qubit. The qubit is a two-level quantum system—example qubit systems are the spin of an electron, the polarization of a photon, or a two-level atom with a ground state and an excited state. We do not worry too much about physical implementations in this chapter, but instead focus on the mathematical postulates of the quantum theory and operations that we can perform on qubits.

We progress from qubits to a study of physical qudits. Qudits are quantum systems that have d levels and are an important generalization of qubits. Again, we do not discuss physical realizations of qudits.

Noise can affect quantum systems, and we must understand methods of modeling noise in the quantum theory because our ultimate aim is to construct schemes for protecting quantum systems against the detrimental effects of noise. In Chapter 1, we remarked on the different types of noise that occur in nature. The first, and perhaps more easily comprehensible type of noise, is that which is due to our lack of information about a given scenario. We observe this type of noise in a casino, with every shuffle of cards or toss of dice. These events are random, and the random variables of probability theory model them because the outcomes are unpredictable. This noise is the same as that in all classical information-processing systems.

For Students

Prerequisites for understanding the content in this book are a solid background in probability theory and linear algebra. If you are new to information theory, then there is enough background in this book to get you up to speed (Chapters 2, 10, 12,and 13). Though, classics on information theory such as Cover and Thomas (1991) and MacKay (2003) could be helpful as a reference. If you are new to quantum mechanics, then there should be enough material in this book (Part II) to give you the background necessary for understanding quantum Shannon theory. The book of Nielsen and Chuang (sometimes known as “Mike and Ike”) has become the standard starting point for students in quantum information science and might be helpful as well (Nielsen & Chuang, 2000). Some of the content in that book is available in Nielsen's dissertation (Nielsen, 1998). If you are familiar with Shannon's information theory (at the level of Cover and Thomas (1991), for example), then this book should be a helpful entry point into the field of quantum Shannon theory. We build on intuition developed classically to help in establishing schemes for communication over quantum channels. If you are familiar with quantum mechanics, it might still be worthwhile to review Part II because some content there might not be part of a standard course on quantum mechanics.

In this chapter, we discuss several information measures that are important for quantifying the amount of information and correlations that are present in quantum systems. The first fundamental measure that we introduce is the von Neumman entropy. It is the quantum analog of the Shannon entropy, but it captures both classical and quantum uncertainty in a quantum state. The von Neumann entropy gives meaning to a notion of the information qubit. This notion is different from that of the physical qubit, which is the description of a quantum state in an electron or a photon. The information qubit is the fundamental quantum informational unit of measure, determining how much quantum information is in a quantum system.

The beginning definitions here are analogous to the classical definitions of entropy, but we soon discover a radical departure from the intuitive classical notions from the previous chapter: the conditional quantum entropy can be negative for certain quantum states. In the classical world, this negativity simply does not occur, but it takes a special meaning in quantum information theory. Pure quantum states that are entangled have stronger-than-classical spatial correlations and are examples of states that have negative conditional entropy. The negative of the conditional quantum entropy is so important in quantum information theory that we even have a special name for it: the coherent information. We discover that the coherent information obeys a quantum data-processing inequality, placing it on a firm footing as a particular informational measure of quantum correlations.

We cannot overstate the importance of Shannon's contribution to modern science. His introduction of the field of information theory and his solutions to its two main theorems demonstrate that his ideas on communication were far beyond the other prevailing ideas in this domain around 1948.

In this chapter, our aim is to discuss Shannon's two main contributions in a descriptive fashion. The goal of this high-level discussion is to build up the intuition for the problem domain of information theory and to understand the main concepts before we delve into the analogous quantum information-theoretic ideas. We avoid going into deep technical detail in this chapter, leaving such details for later chapters where we formally prove both classical and quantum Shannon-theoretic coding theorems. We do use some mathematics from probability theory, namely, the law of large numbers.

We will be delving into the technical details of this chapter's material in later chapters (specifically, Chapters 10, 12, and 13). Once you have reached later chapters that develop some more technical details, it might be helpful to turn back to this chapter to get an overall flavor for the motivation of the development.

Data Compression

We first discuss the problem of data compression. Those who are familiar with the Internet have used several popular data formats such as JPEG, MPEG, ZIP, GIF, etc. All of these file formats have corresponding algorithms for compressing the output of an information source.

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.

This chapter begins our exploration of “dynamic” information-processing tasks in quantum Shannon theory, where the term “dynamic” indicates that a quantum channel connects a sender to a receiver and their goal is to exploit this resource for communication. We specifically consider the scenario where a sender Alice would like to communicate classical information to a receiver Bob, and the capacity theorem that we prove here is one particular generalization of Shannon's noisy channel coding theorem from classical information theory (overviewed in Section 2.2). In later chapters, we will see other generalizations of Shannon's theorem, depending on what resources are available to assist their communication or depending on whether they are trying to communicate classical or quantum information. For this reason and others, quantum Shannon theory is quite a bit richer than classical information theory.

The naive approach to communicate classical information over a quantum channel is for Alice and Bob simply to mimic the approach used in Shannon's noisy channel coding theorem. That is, they select a random classical code according to some distribution pX(x), and Bob performs individual measurements of the outputs of a noisy quantum channel according to some POVM. The POVM at the output induces some conditional probability distribution pY∣X(y∣x), which we can in turn think of as an induced noisy classical channel. The classical mutual information I(X; Y) of this channel is an achievable rate for communication, and the best strategy for Alice and Bob is to optimize the mutual information over all of Alice's inputs to the channel and over all measurements that Bob could perform at the output.

This chapter begins our first exciting application of the postulates of the quantum theory to quantum communication. We study the fundamental, unit quantum communication protocols. These protocols involve a single sender, whom we name Alice, and a single receiver, whom we name Bob. The protocols are ideal and noiseless because we assume that Alice and Bob can exploit perfect classical communication, perfect quantum communication, and perfect entanglement. At the end of this chapter, we suggest how to incorporate imperfections into these protocols for later study.

Alice and Bob may wish to perform one of several quantum information-processing tasks, such as the transmission of classical information, quantum information, or entanglement. Several fundamental protocols make use of these resources:

1. 1. We will see that noiseless entanglement is an important resource in quantum Shannon theory because it enables Alice and Bob to perform other protocols that are not possible with classical resources only. We will present a simple, idealized protocol for generating entanglement, named entanglement distribution.

2. 2. Alice may wish to communicate classical information to Bob. A trivial method, named elementary coding, is a simple way for doing so and we discuss it briefly.

3. 3. A more interesting technique for transmitting classical information is superdense coding. It exploits a noiseless qubit channel and shared entanglement to transmit more classical information than would be possible with a noiseless qubit channel alone.

4. […]

This chapter begins our first technical foray into the asymptotic theory of information. We start with the classical setting in an effort to build up our intuition of asymptotic behavior before delving into the asymptotic theory of quantum information.

The central concept of this chapter is the asymptotic equipartition property. The name of this property may sound somewhat technical at first, but it is merely an application of the law of large numbers to a sequence drawn independently and identically from a distribution pX(x) for some random variable X. The asymptotic equipartition property reveals that we can divide sequences into two classes when their length becomes large: those that are overwhelmingly likely to occur and those that are overwhelmingly likely not to occur. The sequences that are likely to occur are the typical sequences, and the ones that are not likely to occur are the atypical sequences. Additionally, the size of the set of typical sequences is exponentially smaller than the size of the set of all sequences whenever the random variable generating the sequences is not uniform. These properties are an example of a more general mathematical phenomenon known as “measure concentration,” in which a smooth function over a high-dimensional space or over a large number of random variables tends to concentrate around a constant value with high probability.

In these first few chapters, our aim is to establish a firm grounding so that we can address some fundamental questions regarding information transmission over quantum channels. This area of study has become known as “quantum Shannon theory” in the broader quantum information community, in order to distinguish this topic from other areas of study in quantum information science. In this text, we will use the terms “quantum Shannon theory” and “quantum information theory” somewhat interchangeably. We will begin by briefly overviewing several fundamental aspects of the quantum theory. Our study of the quantum theory, in this chapter and future ones, will be at an abstract level, without giving preference to any particular physical system such as a spin-1/2 particle or a photon. This approach will be more beneficial for the purposes of our study, but, here and there, we will make some reference to actual physical systems to ground us in reality.

You may be wondering, what is quantum Shannon theory and why do we name this area of study as such? In short, quantum Shannon theory is the study of the ultimate capability of noisy physical systems, governed by the laws of quantum mechanics, to preserve information and correlations. Quantum information theorists have chosen the name quantum Shannon theory to honor Claude Shannon, who single-handedly founded the field of classical information theory, with a groundbreaking 1948 paper (Shannon, 1948).

All physical systems register bits of information, whether it be an atom, an electrical current, the location of a billiard ball, or a switch. Information can be classical, quantum, or a hybrid of both, depending on the system. For example, an atom or an electron or a superconducting system can register quantum information because the quantum theory applies to each of these systems, but we can safely argue that the location of a billiard ball registers classical information only. These atoms or electrons or superconducting systems can also register classical bits because it is always possible for a quantum system to register classical bits.

The term information, in the context of information theory, has a precise meaning that is somewhat different from our prior “everyday” experience with it. Recall that the notion of the physical bit refers to the physical representation of a bit, and the information bit is a measure of how much we learn from the outcome of a random experiment. Perhaps the word “surprise” better captures the notion of information as it applies in the context of information theory.

This chapter begins our formal study of classical information. Recall that Chapter 2 overviewed some of the major operational tasks in classical information theory. Here, our approach is somewhat different because our aim is to provide an intuitive understanding of information measures, in terms of the parties who have access to the classical systems.