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 p X ( 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. The asymptotic equipartition property immediately leads to the intuition behind Shannon's scheme for compressing classical information. The scheme first generates a realization of a random sequence and asks the question: Is the produced sequence typical or atypical? If it is typical, compress it. Otherwise, throw it away. The error probability of this compression scheme is non-zero for any fixed length of a sequence, but it vanishes in the asymptotic limit because the probability of the sequence being in the typical set converges to one, while the probability that it is in the atypical set converges to zero. This compression scheme has a straightforward generalization to the quantum setting, in which we wish to compress qubits instead of classical bits. The bulk of this chapter is here to present the many technical details needed to make rigorous statements in the asymptotic theory of information. We begin with an example, follow with the formal definition of a typical sequence and a typical set, and prove the three important properties of a typical set.
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 p X ( 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. The asymptotic equipartition property immediately leads to the intuition behind Shannon's scheme for compressing classical information. The scheme first generates a realization of a random sequence and asks the question: Is the produced sequence typical or atypical? If it is typical, compress it. Otherwise, throw it away. The error probability of this compression scheme is non-zero for any fixed length of a sequence, but it vanishes in the asymptotic limit because the probability of the sequence being in the typical set converges to one, while the probability that it is in the atypical set converges to zero. This compression scheme has a straightforward generalization to the quantum setting, in which we wish to compress qubits instead of classical bits. The bulk of this chapter is here to present the many technical details needed to make rigorous statements in the asymptotic theory of information. We begin with an example, follow with the formal definition of a typical sequence and a typical set, and prove the three important properties of a typical set.
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.
Chapter 8 explores the asymptotic regime of quantum information processing, beginning with quantum typicality, which illustrates the convergence of quantum states toward a typical form with increasing copies. This leads to the asymptotic equipartition property (AEP), indicating that with a high number of copies, probability vectors become uniformly distributed. The method of types is introduced next, a tool from classical information theory that classifies sequences based on their statistical properties. This is crucial for understanding the behavior of large quantum systems and has implications for quantum data compression. Advancing to quantum hypothesis testing, the chapter outlines efficient strategies for distinguishing between two quantum states through repeated measurements. Central to this is the Quantum Stein’s lemma, which asserts the exponential decline in the error probability of hypothesis testing as the sample size of quantum systems increases. The chapter highlights the deep interplay between typicality, statistical methods, and hypothesis testing, laying the groundwork for asymptotic interconversion of quantum resources.
This chapter marks the beginning of our study of the asymptotic theory of quantum information, where we develop the technical tools underpinning this theory. The intuition for it is similar to the intuition we developed in the previous chapter on typical sequences, but we will find some important differences between the classical and quantum cases. So far, there is not a single known information-processing task in quantum Shannon theory where the tools from this chapter are not helpful in proving the achievability part of a coding theorem. For the most part, we can straight-forwardly import many of the ideas from the previous chapter about typical sequences for use in the asymptotic theory of quantum information. Though, one might initially think that there are some obstacles to doing so. For example, what is the analogy of a quantum information source? Once we have established this notion, how would we determine if a state emitted from a quantum information source is a typical state? In the classical case, a simple way of determining typicality is to inspect all of the bits in the sequence. But there is a problem with this approach in the quantum domain—“looking at quantum bits” is equivalent to performing a measurement and doing so destroys delicate superpositions that we would want to preserve in any subsequent quantum information-processing task. So how can we get around the aforementioned problem and construct a useful notion of quantum typicality? Well, we should not be so destructive in determining the answer to a question when it has only two possible answers.
The classical asymptotic equipartition property is the statement that, in the limit of a large number of identical repetitions of a random experiment, the output sequence is virtually certain to come from the typical set, each member of which is almost equally likely. In this paper, a fully quantum generalization of this property is shown, where both the output of the experiment and side information are quantum. An explicit bound on the convergence is given, which is independent of the dimensionality of the side information. This naturally leads to a family of REacutenyi-like quantum conditional entropies, for which the von Neumann entropy emerges as a special case.
This chapter marks the beginning of our study of the asymptotic theory of quantum information, where we develop the technical tools underpinning this theory. The intuition for it is similar to the intuition we developed in the previous chapter on typical sequences, but we will find some important differences between the classical and quantum cases. So far, there is not a single known information-processing task in quantum Shannon theory where the tools from this chapter are not helpful in proving the achievability part of a coding theorem. For the most part, we can straightforwardly import many of the ideas from the previous chapter about typical sequences for use in the asymptotic theory of quantum information. However, one might initially think that there are some obstacles to doing so. For example, what is the analogy of a quantum information source? Once we have established this notion, how would we determine if a state emitted from a quantum information source is a typical state? In the classical case, a simple way of determining typicality is to inspect all of the bits in the sequence. But there is a problem with this approach in the quantum domain—“looking at quantum bits” is equivalent to performing a measurement and doing so destroys delicate superpositions that we would want to preserve in any subsequent quantum information-processing task. So how can we get around the aforementioned problem and construct a useful notion of quantum typicality? Well, we should not be so destructive in determining the answer to a question when it has only two possible answers. After all, we are only asking “Is the state typical or not?”, and we can be a bit more delicate in the way that we ask this question. As an analogy, suppose Bob is curious to determine whether Alice could join him for dinner at a nice restaurant on the beach. He would likely just phone her and politely ask, “Sweet Alice, are you available for a lovely oceanside dinner?”, as opposed to barging into her apartment, probing through all of her belongings in search of her calendar, and demanding that she join him if she is available.
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 Shannontheoretic 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, 13, and 14). 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. A first glance at the compression problem might lead one to believe that it is not possible to compress the output of the information source to an arbitrarily small size, and Shannon proved that this is the case. This result is the content of Shannon's first noiseless coding theorem. An Example of Data Compression We begin with a simple example that illustrates the concept of an information source. We then develop a scheme for coding this source so that it requires fewer bits to represent its output faithfully. Suppose that Alice is a sender and Bob is a receiver. Suppose further that a noiseless bit channel connects Alice to Bob—a noiseless bit channel is one that transmits information perfectly from sender to receiver, e.g., Bob receives “0” if Alice transmits “0” and Bob receives “1” if Alice transmits “1.”