Founded by Shannon, information theory deals with the fundamental principles of communication. The two most important questions answered by this theory are how much we can compress a given data source and how much data we can transmit in a given communication channel. Information theory is essentially statistically minded. Data sources are modeled as random processes, and transmission channels are also modeled in probabilistic terms. The theory does not deal with the content of information – it deals with the frequency at which symbols (letters, figures, etc.) appear or are processed but not their meaning. A statistical model is not the only option. Non-statistical theories also exist (e.g., Kolmogorov complexity). However, in this section and throughout this book, we will only use the statistical tools. Information theory is of central importance in quantum cryptography. It may be used to model the transmission of the key elements from Alice to Bob. Note that what may happen on the quantum channel is better described using quantum information theory – see Chapter 4. Yet, the key elements chosen by Alice and those obtained by Bob after measurement are classical values so, for instance, the transmission errors can accurately be modeled using classical information theory. Reconciliation, in particular, requires classical information-theoretic techniques. Source coding Source coding is the first problem that information theory addresses. Assume that a source emits symbols x i from an alphabet χ and that it can be modeled by the random variable X on χ. For instance, the source can be the temperature measured by some meteorological station at regular intervals or the traffic on a network connection.
Founded by Shannon, information theory deals with the fundamental principles of communication. The two most important questions answered by this theory are how much we can compress a given data source and how much data we can transmit in a given communication channel. Information theory is essentially statistically minded. Data sources are modeled as random processes, and transmission channels are also modeled in probabilistic terms. The theory does not deal with the content of information – it deals with the frequency at which symbols (letters, figures, etc.) appear or are processed but not their meaning. A statistical model is not the only option. Non-statistical theories also exist (e.g., Kolmogorov complexity). However, in this section and throughout this book, we will only use the statistical tools. Information theory is of central importance in quantum cryptography. It may be used to model the transmission of the key elements from Alice to Bob. Note that what may happen on the quantum channel is better described using quantum information theory – see Chapter 4. Yet, the key elements chosen by Alice and those obtained by Bob after measurement are classical values so, for instance, the transmission errors can accurately be modeled using classical information theory. Reconciliation, in particular, requires classical information-theoretic techniques. Source coding Source coding is the first problem that information theory addresses. Assume that a source emits symbols x i from an alphabet χ and that it can be modeled by the random variable X on χ. For instance, the source can be the temperature measured by some meteorological station at regular intervals or the traffic on a network connection.
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.”
In the history of cryptography, quantum cryptography is a new and important chapter. It is a recent technique that can be used to ensure the confidentiality of information transmitted between two parties, usually called Alice and Bob, by exploiting the counterintuitive behavior of elementary particles such as photons. The physics of elementary particles is governed by the laws of quantum mechanics, which were discovered in the early twentieth century by talented physicists. Quantum mechanics fundamentally change the way we must see our world. At atomic scales, elementary particles do not have a precise location or speed, as we would intuitively expect. An observer who would want to get information on the particle's location would destroy information on its speed – and vice versa – as captured by the famous Heisenberg uncertainty principle . This is not a limitation due to the observer's technology but rather a fundamental limitation that no one can ever overcome. The uncertainty principle has long been considered as an inconvenient limitation, until recently, when positive applications were found. In the meantime, the mid-twentieth century was marked by the creation of a new discipline called information theory . Information theory is aimed at defining the concept of information and mathematically describing tasks such as communication, coding and encryption. Pioneered by famous scientists like Turing and von Neumann and formally laid down by Shannon, it answers two fundamental questions: what is the fundamental limit of data compression, and what is the highest possible transmission rate over a communication channel?
I find that a great part of the information I have was acquired by looking up something and finding something else on the way. Franklin P. Adams The topic of this chapter is quantum information , i.e., information in the quantum world. The material that is presented here lies at the core of a variety of areas within the compass of quantum computation, such as quantum cryptography, described in Chapter 9, and quantum data compression. As quantum information extends and modifies concepts developed in classical information theory, a brief review of the mathematical notion of information is in order. In Section 10.1, we recall the basics of classical information theory. Section 10.2 generalizes this work to get quantum information theory. Section 10.3 discusses classical and quantum data compression. We conclude with a small section on errorcorrecting codes. CLASSICAL INFORMATION AND SHANNON ENTROPY What is information really? In the mid-forties, an American mathematician named Claude Shannon set out to establish a mathematical theory of information on a firm basis. To see this, we use Alice and Bob. Alice and Bob are exchanging messages. Let us say that Alice can only send one of four different messages coded by the letters A, B, C , and D .
Abstract This book deals with the basic concept of information, its importance, and the similarities and differences between classical and quantum information. First, classical information theory and its application to communication are discussed. Quantum mechanics and communication based on the laws of quantum mechanics are then considered. Quantum entanglement, a key resource in quantum communication, is analysed both from the fundamental perspective and from the perspective of its information-processing capability. This book also introduces quantum computation (in the context of the search and factorisation algorithms) and the basics of quantum error correction. Throughout this book, the connections between information theory, thermodynamics, and (quantum) physics are emphasised and discussed. Other topics covered in the book are data compression, related measures of information such as relative entropy, joint entropy, conditional entropy, and mutual information, along with the capacity of a noisy 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.
Information theory, introduced by Claude Shannon in 1948, provides a mathematical model, predominantly probabilistic, for addressing the challenges associated with measuring the amount of information in a message and efficiently and reliably storing the message (compression and protection). This theory has always been intricately connected to communication theory. Information theory not only relies on communication theory but also draws from fields such as statistics, statistical physics, and inference theory. In this chapter, a concise overview is presented, covering the mathematical foundations of classical and quantum information, their manipulation and associated qualifications. The fundamental concepts of classical information theory, including Shannon entropy, joint entropy, conditional entropy, and mutual information, are introduced. Additionally, basic concepts related to quantum information and quantum correlation measurements are presented.