Although the basic ideas of quantum computation are fairly straightforward, the detailed manipulations required to extract a useful result from an entangled superposition of answers can be rather complicated. There are, however, a small number of algorithms which are simple enough to explain using only elementary methods. The best example is Deutsch's algorithm: as this only requires two qubits its properties are amenable to brute-force matrix calculations, and these calculations can be simplified using a variety of short cuts, which also give some insight into how and why the algorithm works. We will also explore the simplest case of Grover's quantum search algorithm, which is once again simple enough to be tacked by brute force. Finally we will look briefly at two methods used to stabilize quantum computers against errors.

Deutsch's algorithm

The invention of Deutsch's algorithm can be taken as defining the start of modern quantum computation, and it remains a key example, exhibiting many of the key properties of quantum algorithms in a particularly simple form. (Note, however, that the version of Deutsch's algorithm described here is not in fact the original but a later modification which is both more powerful and easier to understand.)

Consider a binary function f from one bit to one bit, that is a function which takes in either 0 or 1 as its input and returns either 0 or 1 as its output. There are four such functions which may be conveniently labeled by their outputs as shown in Table 8.1.

We now have all the basic tools we need to describe systems of one and two qubits. In this final chapter of Part I we look at some of the consequences of the peculiar properties of qubits when they are used to encode information. Many of these results can be traced to the properties of quantum measurement.

Measuring a single qubit

A key result in quantum information theory is that it is impossible to accurately characterize a single qubit. In other words, there is no experiment, or sequence of experiments, which allows us to find out the state of a single quantum bit.

The reason for this problem is twofold. Firstly, we have to make some sort of decision about the basis we will use for the measurement. For example, when measuring a single qubit the most popular choice is to make a measurement in the computational basis. This is equivalent to asking the qubit whether it is in state |0⧽ or state |1⧽. If the qubit is indeed in one of the basis states the measurement process is simple, and we will get the obvious answer of 0 if it is in |0⧽ and 1 if it is in |1⧽. If, however, the qubit is in a superposition, such as α|0⧽+β|1⧽, then the situation is more difficult. Characterizing the state now means determining the values of the two complex numbers α and β, but the measurement can only return the answer 0 or 1, and for a superposition state one of these two answers will be returned at random, with probabilities |α|2 and |β|2, respectively.

Quantum physics violates the basic assumptions of local realism. Particles can be entangled with each other in ways that allow correlations stronger than possible in classical physics. This was first realized by Einstein, Podolsky and Rosen (EPR) in 1935 and led them to conclude that quantum theory was incomplete. It took about 30 years before J. S. Bell found observable consequences of this phenomenon by showing how entangled states violate inequalities for two-particle correlations derived purely from the assumption that the world obeys local realism.

Violations of Bell inequalities were first observed experimentally in the Aspect experiment, which will be discussed below. Such experiments are technically challenging and care is needed to avoid any loopholes in the experimental setup that would still permit the description of the experiments by a local realistic theory.

Bell inequalities describe violations of local realism on average, meaning that each individual experimental outcome could occur in a local realistic theory. It is the statistics of these outcomes that violates local realism. In contrast, another class of quantum states, so-called Greenberger–Horne–Zeilinger (GHZ) states, which contain three particles, can be shown to violate local realism in each measurement outcome. We will also discuss this class of states and experiments by Zeilinger's group, which demonstrated this type of violation of local realism for the first time.

Our aim here is not to discuss the exact relations between quantum entanglement, non-locality and realism, and their physical and philosophical implications. While this is a highly interesting topic which attracts a lot of attention from researchers, such an exploration would go beyond the scope of this book.

Scientific progress in physics and mathematics has led to the development of efficient technology for communicating and distributing information in the 20th century. This technology forms one of the cornerstones of information society and our global economy, which are highly reliant on secure methods to transfer and distribute information quickly. To satisfy ever-increasing demands for speed and security, encryption and communication methods are constantly improved and there is an ongoing effort to develop corresponding technology further.

Classical information theory is not usually part of a physics undergraduate degree course. The theory assumes simple classical properties of physical systems and based on those a largely mathematical theory of information is established. The obtained results are independent of the chosen implementation and its physical details. However, one still has to acknowledge that information is physical, that is information carriers, senders, and receivers obey the laws of physics. The notion of quantum information comes about since it turns out that the rules of quantum mechanics violate some of the basic physics assumptions in classical information theory. The consequences of this are many, ranging from improved channel capacities, the possibility of physically secure communication protocols, to invalidating some beliefs about the security of classical communication protocols.

So far the approach followed in this book was to assume idealized physical systemswhich perfectly implement qubits and then demonstrate how quantum computing algorithms can be realized using perfect qubits. Error correction and fault tolerance were only mentioned briefly.

As discussed in Part I of this book, a qubit can in principle be encoded using two energy levels in an atom or ion. These levels are frequently referred to as |g⧽ and |e⧽, suggesting the ground state and some excited state, but the actual choice of levels is made so as to optimize the behavior of the system, and it is common to use two hyperfine sublevels of the ground state. As usual, we will simply call the levels |0⧽ and |1⧽. A quantum computer must, of course, have more than one qubit, and this is achieved by using more than one atom or ion, with one qubit encoded on each physical object. In order to make this approach practical, however, it is essential to trap the atoms or ions so that they can be held in a well-controlled environment where they can easily be manipulated. This can be achieved using electric and magnetic fields.

The use of trapped ions was one of the first proposals for building quantum computers, and is still one of the best developed. Proposals involving trapped atoms are slightly more recent, and have both substantial advantages and disadvantages in comparison with trapped ions. These differences can ultimately be traced back to the fact that ions interact strongly with their environment and have long-range interactions with one another, while atoms interact more weakly and over shorter ranges. Comparing and contrasting the two approaches provides a useful general introduction to the problems underlying many other proposals.

Ion traps

It is relatively easy to trap an ion as it will interact strongly with an electric field through the Coulomb interaction.

As we have seen, even a single qubit is a surprisingly interesting object. However, the real power of quantum information processing begins with systems of two or more qubits. Before studying these in detail we need to expand our notation a little.

Consider a system of two qubits, labeled a and b, each of which has two basis states, |0⧽ and |1⧽. The whole system then has four basis states, which can be written as |0a0b⧽, |0a1b⧽, |1a0b⧽ and |1a1b⧽, and can be found in any general superposition of these states, so that it occupies a four-dimensional Hilbert space. In the same way, a system of three qubits inhabits an eight-dimensional Hilbert space, and so on. This exponential increase in the size of the Hilbert space with a linear increase in the number of qubits underlies the power of quantum computers.

Direct products

The size of the Hilbert spaces involved can also be a huge problem, however, making it difficult to describe states of systems with many qubits. A partial solution is to note that some states can be described in a simpler way, using the concept of direct products. These states, in which the individual qubits can in principle be discussed separately, make up a tiny minority of the states accessible to a multi-qubit system, but include many important states, most notably the basis states. States of this kind are said to be separable, and states which are not separable are said to be entangled. Entangled states are much more interesting than separable ones, but it is wise to begin with the simpler case.

Throughout this text we assume that the reader is familiar with elementary quantum mechanics and the properties of complex vector spaces, and in this appendix we provide a brief reminder of these topics. In particular, we introduce Dirac's notation for describing quantum mechanical systems. Many areas of quantum mechanics studied in undergraduate degrees can be described without using Dirac notation, and its importance is unclear. In other areas, however, the advantages of Dirac notation are huge, and it is essentially the only notation in use. This is particularly true of quantum information theory.

Dirac's notation is closely related to that used to describe abstract vector spaces known as Hilbert spaces, and many formal arguments about the properties of quantum systems are in fact arguments about the properties of Hilbert spaces. Here we aim to steer a careful course between the twin perils of excessive mathematical sophistication and of taking too much on trust. We will not prove some elementary results whose proof can be found elsewhere, but will concentrate on how these results can be used.

Hilbert space

A Hilbert space is an abstract vector space. As such, it has many properties in common with the use of ordinary three-dimensional vectors, but it also differs in several important ways. Firstly, the vector space is not three-dimensional, but can have any number of dimensions. (The description below largely assumes that the number of dimensions is finite, but it is also possible to extend these results to infinite-dimensional spaces.) Secondly, when the vectors are multiplied by scalar numbers these numbers can be complex.

In Part II of this book we show how computations can be implemented using quantum systems. As we will see, the differences between bits and qubits, briefly outlined in Part I, lead to some important consequences for quantum computing. We begin with a brief introduction to the fundamental principles underlying quantum computing: specific implementations will be considered in later chapters.

Reversible computing

While quantum computation in its modern form is still a relatively young discipline, researchers have been interested in the relationship between quantum mechanics and computing for a long time. Early workers were not interested in the ideas of quantum parallelism, which will be explored in the next section, but rather in the question of whether explicitly quantum mechanical systems could be used to implement classical computations. In addition to its intrinsic interest, there are two technological reasons why this might be considered an important question.

The first reason is a direct consequence of Moore's laws. After the development of integrated circuits, computing technology began its headlong dash down the twin roads of ever-faster and ever-smaller devices. These two phenomena are closely related: as computing devices must communicate within themselves, and as the speed of information transfer cannot exceed the speed of light, faster computers must indeed be smaller. There is, however, a limit to this process, defined by the atomic scale: once the size of individual transistors becomes comparable with that of atoms, the old-fashioned approach of micro-electronics becomes completely untenable.

Classical information processing is performed using bits, which are just two-state systems, with the two states called 0 and 1. By grouping bits togetherwe can represent arbitrary pieces of information, and by manipulating these bits we can perform arbitrary computations. The corresponding basic element used in quantum information is the quantum bit, or qubit. This is simply a quantum system with two orthonormal basis states, which we shall call |0⧽ and |1⧽.

There are many possible physical implementations of a qubit, such as spin states of electrons or atomic nuclei, charge states of quantum dots, atomic energy levels, vibrational states of groups of atoms, polarization states of photons, or paths in an interferometer. At this stage the physical implementation is not important: the idea of a qubit is to abstract the discussion away from physical details. Taking the standard approach of quantum information theory, we shall begin by not worrying too much about the properties of these states, or even what their energies are; we shall simply assume that they are eigenstates of the system's Hamiltonian with known eigenvalues (that is, known energies). This approach allows us to concentrate on the fundamental properties of the system, without considering all the tedious details.

We can in principle perform classical information processing on our quantum system by using the two states |0⧽ and |1⧽ as our logical states 0 and 1 and proceeding in the usual fashion, giving rise to the field of reversible computing, which will be explored briefly in Part II. This, however, misses the point.

Cryptographic protocols can be classified by the type of security against eavesdropping which they provide. There exist mathematically secure schemes whose security relies on mathematical proofs (like the Vernam cipher discussed below) or conjectures (like public key RSA encryption) about the complexity of deciphering the message without possessing the correct key. The majority of current secure public Internet connections rely on such schemes. Alternatively, a cryptographic setup may provide a physically secure method for communicating. In these setups the security is provided by the physical laws governing the communication protocol. Here we first discuss a provably secure classical communication protocol and then quantum methods for distributing the necessary keys. The BB84 protocol relies on the impossibility of perfectly distinguishing non-orthogonal quantum states from one copy of the quantum system. The scheme was invented in 1984 and is the first of its kind. In contrast, the Ekert91 protocol makes use of Bell correlations between entangled pairs of photons. These correlations are destroyed when Eve attempts to make a measurement on one of the particles but also when imperfections, such as decoherence processes, affect the scheme. As long as no such “elements of reality” are introduced, and Bell correlations violating local realism can be generated by Alice and Bob, no eavesdropper can be present.

One-time pads and the Vernam cipher

The Vernam cipher is a cryptographic protocol which allows the encryption and decryption protocol to be publicly known. The security of the protocol relies entirely on the key which is private and not publicly known. Alice and Bob share identical n-bit secret key strings (one-time pad).

Why yet another book on quantum information theory? Like many lecturers we began writing this text because none of the alternatives seemed quite right. This book is aimed squarely at undergraduate physics students who want a brief but reasonably thorough introduction to the exciting ideas of quantum information, including its applications in computation and communication. It is based on a short course we have taught to fourth-year students at Oxford University since 2004; for the most part it only assumes knowledge of elementary quantum mechanics and linear algebra, and so could even be taught to third-year undergraduates. A brief revision guide to quantum mechanics is provided as an appendix, which should cover any minor points that have been missed.

As the title implies the book is structured in three parts, starting with the basics of quantum information and then applying this to quantum computation and quantum communication. Part I is self-contained, but contains only the barest hints of the exciting applications which attract many people to this field and so might prove unsatisfying on its own. Parts II and III draw heavily on Part I, but are largely independent of each other, and it would be perfectly possible to study only one of these two without the other.

As this text is aimed at physics undergraduates, we believe that it is vital to cover experimental techniques, rather than merely presenting quantum information as a series of abstract quantum operations. We have, however, concentrated on the basic ideas underlying each approach, rather than worrying about particular experimental details.