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 .
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 .
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.
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.
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 paper (Shannon, 1948). In particular, the name refers to the asymptotic theory of quantum information, which is the main topic of study in this book. Information theorists since Shannon have dubbed him the “Einstein of the information age.”1 The name quantum Shannon theory is fit to capture this area of study because we often use quantum versions of Shannon's ideas to prove some of the main theorems in quantum Shannon theory. We prefer the name “quantum Shannon theory” over such names as “quantum information science” or just “quantum information.” These other names are too broad, encompassing subjects as diverse as quantum computation, quantum algorithms, quantum complexity theory, quantum communication complexity, entanglement theory, quantum key distribution, quantum error correction, and even the experimental implementation of quantum protocols.
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.
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).
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.”