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.

This book covers many major developments in quantum computing, but the field is still young, and there will no doubt be many more developments in the future. These future developments will include research discoveries, of course, but they will also include trends in industry, surges in media coverage, and tides of public interest. This appendix describes tools that can help you track quantum developments of all kinds.

KEEPING ABREAST OF POPULAR NEWS

There are scores of newspapers, magazines, and other popular news sources, any one of which might run a story about the newest quantum development. How will you know if one does? You can keep an eye on your favorite news sources, but you will miss many stories that way. A better tactic is to use a news aggregator, such as Google News (http://news.google.com/), which allows you to search current and past stories from a multitude of news sources. You can add Google News to your stable of frequently visited sites, but the most efficient way to use it is to set up an alert or RSS feed and let the news come to you. After you perform a Google News search that yields good results, simply click “Alerts” to set up an alert that will notify you by e-mail of new stories that satisfy your search. Alternatively, click “RSS” to set up an RSS feed that will deliver those stories directly to your RSS reader.

In this chapter we explore the merging of quantum computation and classical cryptography. This is a new and exciting field of pure and applied research known as quantum cryptography.

We begin with the basics of classical cryptography in Section 9.1. Section 9.2 demonstrates a quantum cryptographic protocol that uses two different bases. We improve on this in Section 9.3, where a protocol with one basis is employed. Section 9.4 shows how to use entanglement to secretly send a message. We conclude with Section 9.5, in which teleportation is demonstrated.

CLASSICAL CRYPTOGRAPHY

Before delving into quantum cryptography, we need to familiarize ourselves with the core ideas of classical cryptography. A good place to start is the following definition.

Definition 9.1.1 Cryptographyis the art of concealing messages.

Indeed, this is precisely what the etymology reveals: “Cryptography” is a compound of two Greek words, crypton and graphein, which mean, respectively, hidden and writing.

Turning an ordinary message into an indecipherable one is called encryption. The opposite action, i.e., restoring the original message, is decryption. The original message is generally referred to as the plaintext, and the encrypted message is the ciphertext. A method for encryption is often referred to as an encryption protocol.

Although its history is relatively recent, quantum computing is already, by all standards, a very broad area of research. There is simply no way we can cover anything more than a relatively small fraction of its interesting topics. There are also many fascinating themes that are not exactly part of quantum computing per se, but are nevertheless closely related to it.

In this appendix, we list a number of suggestions for further exploration, covering some items we omitted from our text. It is our sincere hope that students will find them useful for their presentations or perhaps inspire them to select others that they can discover on their own.

Note to the student: Now it is your turn! The best way to really learn something is to teach it. There is no substitute for spending hours preparing a lecture and getting ideas straight so that you can present them. Knowing that other people will be asking you questions and learning from you will force you to understand the material at a deeper level.

You are urged to choose a subject from an area that you find interesting. Much time and energy is going to be spent learning, understanding, and preparing, so you might as well enjoy your choice from the start.

Complex numbers lie at the very core of quantum mechanics and are therefore absolutely essential to a basic understanding of quantum computation. In this chapter we present this important system of numbers from both the algebraic and the geometric standpoints. Section 1.1 presents some motivation and the basic definitions. The algebraic structure and operations on complex numbers are given in Section 1.2. The chapter concludes with Section 1.3, where complex numbers are presented from a geometric point of view and advanced topics are discussed. Our hope is that this chapter will help you get a little closer to what Sir Roger Penrose has very aptly called the “magic of complex numbers” (Penrose, 2005).

BASIC DEFINITIONS

The original motivation for the introduction of complex numbers was the theory of algebraic equations, the part of algebra that seeks solutions of polynomial equations.

Now that we have the mathematical and physical preliminaries under our belt, we can move on to the nuts and bolts of quantum computing. At the heart of a classical computer is the notion of a bit and at the heart of quantum computer is a generalization of the concept of a bit called a qubit, which shall be discussed in Section 5.1. In Section 5.2, classical (logical) gates, which manipulate bits, are presented from a new and different perspective. From this angle, it is easy to formulate the notion of quantum gates, which manipulate qubits. As mentioned in Chapters 3 and 4, the evolution of a quantum system is reversible, i.e., manipulations that can be done must also be able to be undone. This “undoing” translates into reversible gates, which are discussed in Section 5.3. We move on to quantum gates in Section 5.4.

BITS AND QUBITS

What is a bit?

Definition 5.1.1Abitis a unit of information describing a two-dimensional classical system.

There are many examples of bits:

1. ▪ A bit is electricity traveling through a circuit or not (or high and low).

2. ▪ A bit is a way of denoting “true” or “false.”

3. […]

Quantum theory is cast in the language of complex vector spaces. These are mathematical structures that are based on complex numbers. We learned all that we need about such numbers in Chapter 1. Armed with this knowledge, we can now tackle complex vector spaces themselves.

Section 2.1 goes through the main example of a (finite-dimensional) complex vector space at tutorial pace. Section 2.2 provides formal definitions, basic properties, and more examples. Each of Section 2.3 through Section 2.7 discusses an advanced topic.

Introduction

Let us now return to our original problem from Chapter 2: receiver design. Our ultimate goal is to recover (in an optimal manner) the transmitted information bits b from the received waveform r(t). In this chapter, we will formulate an inference problem that will enable us to achieve this task. In the first stage the received waveform is converted into a suitable observation y.We then create a factor graph of the distribution p(B, Y = y|M). This factor graph will contain three important nodes, expressing the relationship between information bits and coded bits (the decoding node), between coded bits and coded symbols (the demapping node), and between coded symbols and the observation (the equalization node). Correspondingly, the inference problem breaks down into three sub-problems: decoding, demapping, and equalization.

Decoding will be covered in Chapter 8, where we will describe some state-of-the-art iterative decoding take over schemes, including turbo codes, RA codes, and LDPC codes. The demapping problem will be considered in Chapter 9 for two common modulation techniques: bit-interleaved coded modulation and trellis-coded modulation. Equalization highly depends on the specific digital communication scheme. In Chapter 10, we will derive several general-purpose equalization strategies. In the three subsequent chapters, we will then show how these general-purpose strategies can be applied to the digital communication schemes from Chapter 2. In Chapter 11 the focus is on single-user, single-antenna communication.

Motivation

Claude E. Shannon was one of the great minds of the twentieth century. In the 1940s, he almost single-handedly created the field of information theory and gave the world a new way to look at information and communication. The channel-coding theorem, where he proved the existence of good error-correcting codes to transmit information at any rate below capacity with an arbitrarily small probability of error, was one of his fundamental contributions. Unfortunately, Shannon never described how to construct these codes. Ever since his 1948 landmark paper “A mathematical theory of communication” [1], the channel-coding theorem has tantalized researchers worldwide in their quest for the ultimate error-correcting code. After more than forty years, state-of-the-art errorcorrecting codes were still disappointingly far away from Shannon's theoretical capacity bound. No drastic improvement seemed to be forthcoming, and researchers were considering a more practical capacity benchmark, the cut-off rate [2], which could be achieved by practical codes.

In 1993, two until then little-known French researchers from the ENST in Bretagne, Claude Berrou and Alain Glavieux, claimed to have discovered a new type of code, which operated very close to Shannon capacity with reasonable decoding complexity. The decoding process consisted of two decoders passing information back and forth, giving rise to the name “turbo code.” They first presented their results at the IEEE International Conference on Communications in Geneva, Switzerland [3]. Quite understandably, they were met with a certain amount of skepticism by the traditional coding community. Only when their findings were reproduced by other labs did the turbo idea really take off.

Introduction

Before we can even consider designing iterative receivers, we have a lot of ground to cover. The ultimate goal of the receiver is to recover optimally the sequence of information bits that was sent by the transmitter. Since these bits were random in the first place, and they are affected by random noise at the receiver, we need to understand and quantify this randomness, and incorporate it into the design of our receiver.We need to specify what it means to recover optimally the information bits from the received signal. Optimal in what sense? To answer this problem, we call on estimation theory, which will allow us to formulate a suitable optimization problem, the solution of which will give our desired optimal data recovery. Unfortunately, as is common to most optimization problems of any practical relevance, the issue of finding a closed-form solution is intractable. There exists a set of tools that can solve these problems approximately by means of sampling. They go under the name of Monte Carlo (MC) techniques and can help in describing difficult distributions, and in obtaining their characteristics, by means of a list of samples. These MC methods will turn out to be very useful in the factor-graph framework.

This chapter is organized as follows.

• We will start with the basics of Bayesian estimation theory in Section 3.2, covering some important estimators both for discrete and for continuous parameters.

• In Section 3.3, we will provide a brief introduction to MC techniques, including particle representations of distributions, importance sampling, and Markov-chain Monte Carlo (MCMC) methods.

Introduction

As with any good story, it is best to start at the very beginning. Digital communication deals with the transmission of binary information (obtained as the output of a source encoder) from a transmitter to a receiver. The transmitter converts the binary information to an analog waveform and sends this waveform over a physical medium, such as a wire or open space, which we will call the channel. As we shall see, the channel modifies the waveform in several ways. At the receiver, this modified waveform is further corrupted due to thermal noise. Not only does the receiver have to recover the original binary information, but also it must deal with channel effects, thermal noise, and synchronization issues. All in all, the receiver has the bad end of the deal in digital communications. For this reason, this book deals mainly with receiver design, and only to a very small extent with the transmitter.

In this chapter we will describe several digital transmission schemes, detailing how binary information is converted into a waveform at the transmitter side, and how a corrupted version of this waveform arrives at the receiver side. Right now, our focus is not on how the corresponding receivers should be designed. Since there is a myriad of digital transmission schemes, we are obliged to limit ourselves to some of the most important ones.

In early 2002, I was absent-mindedly surfing the Internet, vaguely looking for a tutorial on turbo codes. My PhD advisor at Ghent University, Marc Moeneclaey, thought it wise for his new students to become familiar with these powerful error-correcting codes. Although I finally settled on W. E. Ryan's “A turbo code tutorial,” my search led me (serendipitously?) to the PhD thesis of NiclasWiberg. This thesis shows how to describe codes by means of a (factor) graph, and how to decode them by passing messages on this graph. Although interesting, the idea seemed a bit far-fetched, and I didn't fully appreciate or understand its significance. Nevertheless, Wiberg's thesis stayed in the back of my mind (or at least, I'd like to think so now).

During 2002 and 2003, I worked mainly on synchronization and estimation algorithms for turbo and LDPC codes. A colleague of mine, Justin Dauwels, who was at that time a PhD student of Andy Loeliger at the ETH in Zürich, had developed a remarkable synchronization algorithm for LDPC codes, based on Wiberg's factor graphs. Justin was interested in comparing his synchronization algorithm with ours, and became a visiting researcher in our lab for the first two months of 2004. I fondly remember many hours spent in the department lunchroom, with Justin (painstakingly) explaining the intricacies of factor graphs to me. His discussions motivated me to re-write my source code for decoding turbo and LDPC codes using the factor-graph framework.

Introduction

Error-correcting codes are a way to protect a binary information sequence against adverse channel effects by adding a certain amount of redundancy. This is known as encoding. The receiver can then try to recover the original binary information sequence, using a decoder. The field of coding theory deals with developing and analyzing codes and decoding algorithms. Although coding theory is fairly abstract and generally involves a great deal of math, our knowledge of factor graphs will allow us to derive decoding algorithms without delving too deep. As we will see, using factor graphs, decoding becomes a fairly straightforward matter. In contrast to conventional decoding algorithms, our notation will be the same for all types of codes, which makes it easier to understand and interpret the algorithms.

In this chapter, we will deal with four types of error-correcting codes: repeat–accumulate (RA) codes, low-density parity-check (LDPC) codes, convolutional codes, and turbo codes. Repeat–accumulate codes were introduced in 1998 as a type of toy code. Later they turned out to have a great deal of practical importance [81]. We then move on to the LDPC codes, which were invented by Gallager in 1963 [50], and reintroduced in the early 1990s by MacKay [82]. Both types of codes can easily be cast into factor graphs; these factor graphs turn out to have cycles, leading to iterative decoding algorithms. Convolutional codes, on the other hand, are based on state-space models and thus lead to cycle-free factor graphs [83].