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.
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.
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.”
Information theory lies at the heart of modern technology, underpinning all communications, networking, and data storage systems. This book sets out, for the first time, a complete overview of both classical and quantum information theory. Throughout, the reader is introduced to key results without becoming lost in mathematical details. Opening chapters present the basic concepts and various applications of Shannon's entropy, moving on to the core features of quantum information and quantum computing. Topics such as coding, compression, error-correction, cryptography and channel capacity are covered from classical and quantum viewpoints. Employing an informal yet scientifically accurate approach, Desurvire provides the reader with the knowledge to understand quantum gates and circuits. Highly illustrated, with numerous practical examples and end-of-chapter exercises, this text is ideal for graduate students and researchers in electrical engineering and computer science, and practitioners in the telecommunications industry. Further resources and instructor-only solutions are available at www.cambridge.org/9780521881715.
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.
This book is intended as an introductory textbook at graduate or advanced undergraduate level. Students with diverse backgrounds, in mathematics, physics and computer science, can use it to become acquainted with the quantum theory of information. Its scope is deliberately chosen to be not too broad, while being self-consistent and usable for a semester-long course for beginners. The subject is presented using a balanced mix of intuitive arguments and rigorous formalism. The emphasis is not on the physical interpretation, but rather on the formal and mathematical features of quantum information theory, in order to be accessible from different backgrounds, the only requirement being a basic knowledge of linear algebra. In particular, a background in quantum mechanics is not needed, since quantum theory is used as a mere mathematical framework without entering into physical interpretations. The book introduces all necessary concepts from quantum theory and classical information theory, to cover the elements of quantum Shannon theory: quantum states and channels, data compression and entropy, error correcting codes and channel capacities, as well as the basics of entanglement theory and quantum cryptography. Examples are provided to help the reader in understanding the different concepts, together with exercises at the end of each chapter.
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 should be enough background in this book to get you up to speed (Chapters 2, 10, 13, and 14). However, classics on information theory such as Cover & Thomas (2006) 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 & Chuang (2000), sometimes affectionately known as “Mike and Ike”, has become the standard starting point for students in quantum information science and might be helpful as well. Some of the content of that book is available in the dissertation of Nielsen (1998). If you are familiar with Shannon's information theory (at the level of Cover & Thomas, 2006, for example), then the present 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. The aim of this book is to develop “from the ground up” many of the major, exciting pre- and post-millennium developments in the general area of study known as quantum Shannon theory. As such, we spend a significant amount of time on quantum mechanics for quantum information theory (Part II), we give a careful study of the important unit protocols of teleportation, super-dense coding, and entanglement distribution (Part III), and we develop many of the tools necessary for understanding information transmission or compression (Part IV). Parts V and VI are the culmination of this book, where all of the tools developed come into play for understanding many of the important results in quantum Shannon theory.
The astute reader might have formed the impression that quantum in formation science is a rather qualitative discipline because we have not, as yet, explained how to quantify quantum information. There are three good reasons for leaving this important question until the final chapter. Firstly, quantum information theory is technically demanding and to treat it at an earlier stage might have suggested that our subject was more complicated than it is. Secondly, there is the fact that many of the ideas in the field, such as teleportation and quantum circuits, are unfamiliar and it was important to present these as simply as possible. Finally, and most importantly, the theory of quantum information is not yet fully developed. It has not yet reached, in particular, the level of completeness of its classical counterpart. For this reason we can answer only some of the many questions we would like a quantum theory of information to address. Having said this, we can say that however, there are beautiful and useful mathematical results and it seems certain that these will continue to form an important part of the theory as it develops. We noted in the introduction to Chapter 1 that ‘quantum mechanics is a probabilistic theory and so it was inevitable that a quantum information theory would be developed’. A presentation of at least the beginnings of a quantitative theory is the objective of this final chapter. The entropy or information derived from a given probability distribution is, as we have seen, a convenient measure of the uncertainty associated with the distribution. If many of the probabilities are large, so that many of the possible events are comparably likely, then the entropy will be large. If one probability is close to unity, however, then the entropy will be small. It is convenient to introduce entropy in quantum mechanics as a measure of the uncertainty, or lack of knowledge, of the form of the state vector. If we know that our system is in a particular pure state then the associated uncertainty or entropy should be zero. For mixed states, however, it will take a non-zero value.