The aim of this book is to give an introduction to quantum computing that anyone who is comfortable with high school mathematics and is willing to put in a little work can understand. We will study qubits, entanglement, quantum teleportation, and quantum algorithms, among other quantum-related topics. The goal is not to give some vague idea of these concepts but to make them crystal clear.
Quantum computing is often in the news: China teleported a qubit from earth to a satellite; Shor’s algorithm has put our current encryption methods at risk; quantum key distribution will make encryption safe again; Grover’s algorithm will speed up data searches. But what does all this really mean? How does it all work? All of this will be explained.
Can this be done without using mathematics? No, not if we want to really understand what is going on. The underlying ideas come from quantum mechanics and are often counterintuitive. Attempts to describe these in words don’t work because we have no experience of them in our everyday lives. Even worse, verbal descriptions often give the impression that we have understood something when we really haven’t. The good news is that we really do not need to introduce much mathematics. My role as a mathematician is to simplify the mathematics as much as possible—just sticking to the absolute essentials—and to give elementary examples to illustrate both how it is used and what it means. That said, the book probably contains mathematical ideas that you have not seen before, and, as with all mathematics, new concepts can seem strange at first. It is important not to gloss over the examples but to read them carefully, following each step of the calculations.
Quantum computing is a beautiful fusion of quantum physics with computer science. It incorporates some of the most stunning ideas of physics from the twentieth century into an entirely new way of thinking about computation. The basic unit of quantum computing is the qubit. We will see what qubits are and what happens when we measure them. A classical bit is either 0 or 1. If it’s 0 and we measure it, we get 0. If it’s 1 and we measure 1, we get 1. In both cases the bit remains unchanged. The situation is totally different for qubits. A qubit can be in one of an infinite number of states—a superposition of both 0 and 1—but when we measure it, as in the classical case, we just get one of two values, either 0 or 1. The act of measurement changes the qubit. A simple mathematical model describes all of this precisely.
Qubits can also be entangled. When we make a measurement of one of them, it affects the state of the other. Again, this is something that we don’t experience in our daily lives, but it is described perfectly by our mathematical model.
These three things—superposition, measurement, and entanglement—are the key quantum mechanical ideas. Once we know what they mean, we can see how they may be used in computations. It is here that human ingenuity enters the picture.
Mathematicians often describe proofs as being beautiful, often containing unexpected insights. I feel exactly the same way about many of the topics we will look at. Bell’s theorem, quantum teleportation, superdense coding, all are gems. The error correcting circuit and Grover’s algorithm are absolutely amazing.
By the end of the book, you should understand the basic ideas that underlie quantum computing, and you will have seen some ingenious and beautiful constructions. You will also come to realize that quantum computing and classical computing are not two distinct disciplines, but that quantum computing is the more fundamental form of computing—anything that can be computed classically can be computed on a quantum computer. The qubit is the basic unit of computation, not the bit. Computation, in its essence, really means quantum computation.
Finally, it should be emphasized that this book is about the theory of quantum computation. It is about software, not hardware. We briefly mention hardware in places and occasionally talk about how to physically entangle qubits, but these topics are just asides. The book is not about how to build a quantum computer, but how to use one.
Here’s a brief description of the book’s contents.
Chapter 1. The basic unit of classical computing is the bit. Bits can be represented by anything that can be in one of two possible states. The standard example is an electrical switch that can be either on or off. The basic unit of quantum computing is the qubit. This can be represented by the spin of an electron or the polarization of a photon, but the properties of spin and polarization are not nearly as familiar to us as a switch being in the on or off position.
We look at the basic properties of spin, starting with Otto Stern and Walther Gerlach’s classic experiment in which they studied the magnetic properties of silver atoms. We see what happens when we measure spin in a number of different directions. The act of making a measurement can affect the state of a qubit. There is also an underlying randomness associated with some of the measurements that we will need to explain.
The chapter concludes by showing that experiments analogous to those for spin can be performed using polarized filters and ordinary light.
Chapter 2. Quantum computing is based on an area of mathematics called linear algebra. Fortunately, we only need a few concepts. This chapter introduces and describes the linear algebra we need and illustrates how it is going to be used in the later chapters.
We introduce vectors and matrices and show how to calculate the length of vectors and how to tell whether or not two vectors are perpendicular. The chapter starts by just considering elementary operations on vectors and then shows how matrices give a simple way of doing a number of these calculations simultaneously.
It is not initially apparent that this material is going to be useful, but it is. Linear algebra forms the foundation of quantum computing. Since the rest of the book uses the mathematics introduced here, this chapter needs to be read carefully.
Chapter 3. This chapter shows how the previous two chapters are connected. The mathematical model of spin or, equivalently, that of polarization is given using linear algebra. This enables us to give the definition of a qubit and to describe exactly what happens when we measure it.
Several examples of measuring qubits in different directions are given. The chapter ends with an introduction to quantum cryptography, describing the BB84 protocol.
Chapter 4. This chapter describes what it means for two qubits to be entangled. Entanglement is difficult to describe in words, but it is easy to describe mathematically. The new mathematical idea is the tensor product. This is the simplest way of combining mathematical models of individual qubits to give one model that describes a collection of qubits.
Though the mathematics is straightforward, entanglement is not something that we experience in everyday life. When one of a pair of entangled qubits is measured, it affects the second qubit. This is what Albert Einstein, who disliked it, called “spooky action at a distance.” We look at several examples.
The chapter concludes by showing that we can’t use entanglement to communicate faster than the speed of light.
Chapter 5. We look at Einstein’s concerns with entanglement and whether a hidden variable theory can preserve local realism. We go through the mathematics of Bell’s inequality—a remarkable result that gives an experimental way of determining whether or not Einstein’s argument is correct. As most people know, Einstein’s view was wrong, but even Bell thought he would be proved correct.
Artur Ekert realized that the setup for the test of Bell’s inequality could also be used both to generate a secure key to be used for cryptography and at the same time to test whether any eavesdroppers are present. We conclude the chapter with a description of this cryptographic protocol.
Chapter 6. The chapter starts with standard topics in computation: bits, gates, and logic. Then we briefly look at reversible computation and the ideas of Ed Fredkin. We show that both the Fredkin gate and the Toffoli gate are universal—you can build a complete computer using only Fredkin gates (or Toffoli gates). The chapter concludes with Fredkin’s billiard-ball computer. This is not really needed for the rest of our story, but its sheer ingenuity demands that it be included.
This computer consists of balls colliding with one another and off various walls. It conjures up images of particles interacting. This is one of the ideas that inspired Richard Feynman to become interested in the idea of quantum computing. Feynman wrote some of the earliest papers on the subject.
Chapter 7. This chapter begins the study of quantum computing using quantum circuits. Quantum gates are defined. We see how a quantum gate acts on a qubit and realize that we have been considering these ideas all along. We just need to change our perspective. We no longer think of an orthogonal matrix as acting on our measuring device, but as acting on the qubit. We also prove some amazing results concerning superdense coding, quantum teleportation, cloning, and error correction.
Chapter 8. This is probably the most challenging chapter. In it we look at some quantum algorithms and show how quickly they can compute an answer compared to classical algorithms. To talk about the speed of algorithms we need to introduce various ideas from complexity theory. Once we have defined something called query complexity, we study three quantum algorithms and show that they are faster with respect to this type of complexity than their classical counterparts.
Quantum algorithms exploit the underlying structure of the problem that is being solved. It is much more than just the idea of quantum parallelism—putting the input into a superposition of all possible states. This chapter introduces the last piece of mathematical machinery, the Kronecker product of matrices. But the difficulty of the material is really caused by the fact that we are computing in a completely new way and we have no experience of thinking about solving problems using these novel ideas.
Chapter 9. The last chapter looks at the impact that quantum computing is going to have on our lives. We start by giving brief descriptions of two important algorithms, one invented Peter Shor, the other by Lov Grover.
Shor’s algorithm gives a way of factoring a large number into the product of its prime factors. This might not seem that important, but our Internet security depends on this problem being hard to solve. Being able to factor products of large primes threatens our current methods of securing transactions between computers. It might be some time until we have quantum computers powerful enough to factor the large numbers that are currently in use, but the threat is real, and it is already forcing us to think about how to redesign the ways that computers can securely talk to one another.
Grover’s algorithm is for special types of data searches. We show how it works for a small case and indicate how it works in general. Both Grover’s and Shor’s algorithms are important, not only for the problems they can solve but also for the new ideas they introduce. These underlying ideas have been and are being incorporated into a new generation of algorithms.
After looking at algorithms, we switch gears and briefly look at how quantum computation can be used to simulate quantum processes. Chemistry, at its most basic level, is quantum mechanical. Classical computational chemistry works by taking quantum mechanical equations and simulating them using classical computers. These simulations are approximations and ignore the fine details. This works well in many cases, but in some cases it doesn’t. In these cases you need the fine details, and quantum computers should be able to give them.
This chapter also briefly looks at building actual machines. This is a very fast-growing area. The first machines are being offered for sale. There is even one machine available on the cloud that everyone can use for free. It looks likely that we will soon enter the age of quantum supremacy. (We explain what this means.)
The book concludes with the realization that quantum computation is not a new type of computation but is the discovery of the true nature of computation.