To a very great extent, mankind owes its progress to the ability to communicate, and a key aspect in this ability is the capability of communicating in writing. From the earliest days of writing, there have been occasions when individuals have desired to limit their information to a restricted group of people. They had secrets they wanted to keep. To this end, such individuals developed ideas by means of which their communications could be made unintelligible to those who had not been provided with the special information needed for decipherment. The general techniques used to accomplish such a purpose, i.e. the hiding of the meaning of messages, constitute the study known as cryptography.

Before the development of postal systems and electrical transmission of information, the usual manner of sending a communication was by private messenger. Even under these circumstances the use of the concealment tactics of cryptography was often advisable because of the possibility that the messenger might be apprehended or prove disloyal. In recent times a message transmitted by radio could be copied by anyone having appropriate equipment and listening to the right frequency at the right time. In such a case, a sender desiring privacy of communication would be required to employ some method of cryptographic concealment.

Now, just as the sender of the message attempted to conceal information from any but the desired recipient, there would be individuals very much interested in determining what the message said—most probably the very individuals from whom the sender was trying to keep the information.

Digraphic ciphers based on linear transformations—matrices

We have seen in the previous chapters that various techniques associated with the frequencies of individual letters and their combinations enable the cryptanalyst to cope with different kinds of substitution ciphers. Conceivably this may remain true even for more sophisticated methods of cryptography so long as the unit of cryptography remains a single letter. Perhaps the way for the cryptographer to prevent the cryptanalyst's successes with letter frequencies might be to make the unit of encipherment a group of letters instead of just one. A system of cryptography in which a group of n plain text letters is replaced as a unit by a group of n cipher letters is called a polygraphic system.

In the simplest case, n = 2, the system is called digraphic. Each pair of plain text letters is replaced by a cipher digraph.

There are many different ways to set up the plain-cipher relationships for a digraphic system. For example, a 26 × 26 square can be constructed with the 262 = 676 possible digraphs entered randomly into the cells of the square. Normal alphabets across the top of the square and down the left side serve as plain language coordinates. The cipher equivalent of the plain digraph P1P2 is found in the cell on row P1 and in column P2. A portion of such a square is shown in Figure 4.1. For example, the cipher equivalents for AC, BE, CD are RA, AS, YE.

PLAYING WITH MATLAB

There is no better way to learn than playing. After all, that is how children learn. In this appendix, we are going to provide the basic guidelines for “playing the quantum computing game” with the help of the MATLAB environment.

COMPLEX NUMBERS AND MATRICES

We began this book by saying that complex numbers are fundamental for both quantum mechanics and quantum computing, so we are going to familiarize ourselves with the way they are dealt with in MATLAB.

To begin with, we need to declare complex number variables. This is easy: a complex has a real part and an imaginary part, both double. The imaginary part is declared by using the “i” or “j” character.

Before we formally present quantum mechanics in all its wonders, we shall spend time providing some basic intuitions behind its core methods and ideas. Realizing that computer scientists feel comfortable with graphs and matrices, we shall cast quantum mechanical ideas in graph-theoretic and matrix-theoretic terms. Everyone who has taken a class in discrete structures knows how to represent a (weighted) graph as an adjacency matrix. We shall take this basic idea and generalize it in several straightforward ways. While doing this, we shall present a few concepts that are at the very core of quantum mechanics. In Section 3.1, the graphs are without weights. This will model classical deterministic systems. In Section 3.2, the graphs are weighted with real numbers. This will model classical probabilistic systems. In Section 3.3, the graphs are weighted with complex numbers and will model quantum systems. We conclude Section 3.3 with a computer science/graph-theoretic version of the double-slit experiment. This is perhaps the most important experiment in quantum mechanics. Section 3.4 discusses ways of combining systems to yield larger systems.

Throughout this chapter, we first present an idea in terms of a toy model, then generalize it to an abstract point, and finally discuss its connection with quantum mechanics, before moving on to the next idea.

In this chapter, we discuss a few hardware issues and proposals. Most certainly you have wondered (perhaps more than once!) whether all we have presented up to now is nothing more than elegant speculation, with no practical impact for the real world.

To bring things down to earth, we must address a very basic question: do we actually know how to build a quantum computer?

It turns out that the implementation of quantum computing machines represents a formidable challenge to the communities of engineers and applied physicists. However, there is some hope in sight: quite recently, some simple quantum devices consisting of a few qubits have been successfully built and tested. Considering the amount of resources that have been poured into this endeavor from different quarters (academia, private sector, and the military), it would not be entirely surprising if noticeable progress were made in the near future.

In Section 11.1 we spell out the hurdles that stand in the way, chiefly related to the quantum phenomenon known as decoherence. We also enumerate the wish list of desirable features for a quantum device. Sections 11.2 and 11.3 are devoted to describing two of the major proposals around: the ion trap and optical quantum computers.

This bibliographic essay reviews seminal papers in quantum computing. Although quantum computing is a young science, its researchers have already published thousands of noteworthy articles, far too many to list here. Therefore, this appendix is not a comprehensive chronicle of the emergence and evolution of the field but rather a guided tour of some of the papers that spurred, formalized, and furthered its study.

Quantum computing draws on advanced ideas from computer science, physics, and mathematics, and most major papers were written by researchers conversant in all three fields. Nevertheless, all the articles described in this appendix can be appreciated by computer scientists.

READING SCIENTIFIC ARTICLES

Do not be deterred if an article seems impenetrable. Keep in mind that professors and professionals also struggle to understand these articles, and take comfort in this epigram usually attributed to the great physicist Richard Feynman: “If you think you understand quantum mechanics, you don't understand quantum mechanics.”

Some articles are difficult to understand not only because quantum theory is devilishly elusive but also because scientific writing can be opaque. Fortunately, there are techniques for tackling scientific articles, beginning with these preliminary steps:

1. ▪ Read the title. It may contain clues about the article's purpose or findings.

2. ▪ Read the abstract. It summarizes the article and will help you recognize important points when you read them.

3. ▪ Read the introduction and conclusion. Usually in plain language, the introduction and conclusion will help you decode the rest of the article.

4. […]

In Chapters 1 and 2 we developed the necessary mathematical apparatus and terminology that will be used throughout this book. Chapter 3 has provided some heuristics and gently led us to the threshold of quantum mechanics. It is now time to open the door, introduce the basic concepts and tools of the trade, and continue our journey to quantum computing.

In Section 4.1 we spend a few words on the motivations behind quantum mechanics. We then introduce quantum states and how they are distinguishable from one another through observations. Section 4.2 describes observable physical quantities within the quantum framework. How observable quantities are measured is the topic of Section 4.3. The dynamics of quantum systems, i.e., their evolution in time, is the focus of Section 4.4. Finally, in Section 4.5, we revisit the tensor product and show how it describes the way in which larger quantum systems are assembled from smaller ones. In the process, we meet the crucial notion of entanglement, a feature of the quantum world that pops up again in the chapters ahead.

QUANTUM STATES

Why quantum mechanics? To answer this question, we have to hearken back in time to the dawn of the twentieth century. Classical mechanics still dominated the scene, with its double-pronged approach: particles and waves.

Quantum computing is a fascinating new field at the intersection of computer science, mathematics, and physics, which strives to harness some of the uncanny aspects of quantum mechanics to broaden our computational horizons. This book presents some of the most exciting and interesting topics in quantum computing. Along the way, there will be some amazing facts about the universe in which we live and about the very notions of information and computation.

The text you hold in your hands has a distinct flavor from most of the other currently available books on quantum computing. First and foremost, we do not assume that our reader has much of a mathematics or physics background. This book should be readable by anyone who is in or beyond their second year in a computer science program. We have written this book specifically with computer scientists in mind, and tailored it accordingly: we assume a bare minimum of mathematical sophistication, a first course in discrete structures, and a healthy level of curiosity. Because this text was written specifically for computer people, in addition to the many exercises throughout the text, we added many programming drills. These are a hands-on, fun way of learning the material presented and getting a real feel for the subject.

In this chapter we are going to describe quantum programming, i.e., the art and science of programming a quantum computer. In Section 7.1, we briefly sketch what it means to program a quantum computing device. Section 7.2 covers a simple version of quantum assembler, based on the so-called QRAM architecture. Section 7.3 describes possible steps leading to higher-level programming languages and constructs. We conclude this chapter with Section 7.4, a short discussion on quantum emulators.

PROGRAMMING IN A QUANTUM WORLD

As you are about to read this chapter, you have undoubtedly been exposed to computer programming in a variety of flavors, and are perhaps already an accomplished programmer of real-life applications. Programming a classical machine carries an immediate, unambiguous sense. However, we are going to leave the familiar world of binary chips, and learn how to program some as yet unspecified quantum hardware.

In a sense, theoretical computer science is uniquely qualified to study quantum computing. After all, Alan Turing and the other founders of theoretical computer science studied formal computation long before engineers actually produced a real-life computer. At present, large-scale quantum computers are not a reality yet. Nevertheless, the theoretical analysis of quantum computability and complexity is well on its way.

In Section 8.1, we start with a quick review of some of the basics of deterministic and nondeterministic Turing machines and the complexity classes that they engender. However, we shall discuss them in a way that is easily generalizable for our purposes. Section 8.2 moves on to probabilistic Turing machines and their zoo of complexity classes. Our main objective is found in Section 8.3, where we meet quantum Turing machines and their complexity classes. We shall also state some basic theorems and ideas about quantum computation.

DETERMINISTIC AND NONDETERMINISTIC COMPUTATIONS

Theoretical computer science deals with the question, “What is computable?” We must immediately qualify the question: “computable according to which model of computation?” It turns out that if we omit the question of efficiency, all sufficiently complicated formal models of computation can simulate each other. However, in order to fix our ideas and notation, we have to stick with one and work with it.