10 Introduction and overview Figure 1.1.Classically,if we have two very noisy channels of zero capacity running side by side,then the combined channel has zero capacity to send information.Not surprisingly,if we reverse the direction of one of the channels, we still have zero capacity to send information.Quantum mechanically,reversing one of the zero capacity channels can actually allow us to send information! computation involving two or more parties who may not trust one another.The best known cryptographic problem is the transmission of secret messages.Suppose two parties wish to communicate in secret.For example,you may wish to give your credit card num- ber to a merchant in exchange for goods,hopefully without any malevolent third party intercepting your credit card number.The way this is done is to use a cryptographic protocol.We'll describe in detail how cryptographic protocols work later in the book,but for now it will suffice to make a few simple distinctions.The most important distinction is between private key cryptosystems and public key cryptosystems. The way a private key cryptosystem works is that two parties,'Alice'and Bob',wish to communicate by sharing a private key,which only they know.The exact form of the key doesn't matter at this point-think of a string of zeroes and ones.The point is that this key is used by Alice to encrypt the information she wishes to send to Bob.After Alice encrypts she sends the encrypted information to Bob,who must now recover the original information.Exactly how Alice encrypts the message depends upon the private key,so that to recover the original message Bob needs to know the private key,in order to undo the transformation Alice applied. Unfortunately,private key cryptosystems have some severe problems in many contexts. The most basic problem is how to distribute the keys?In many ways,the key distribution problem is just as difficult as the original problem of communicating in private-a malevolent third party may be eavesdropping on the key distribution,and then use the intercepted key to decrypt some of the message transmission. One of the earliest discoveries in quantum computation and quantum information was that quantum mechanics can be used to do key distribution in such a way that Alice and Bob's security can not be compromised.This procedure is known as quantum cryptog- raphy or quantum key distribution.The basic idea is to exploit the quantum mechanical principle that observation in general disturbs the system being observed.Thus,if there is an eavesdropper listening in as Alice and Bob attempt to transmit their key,the presence of the eavesdropper will be visible as a disturbance of the communications channel Alice and Bob are using to establish the key.Alice and Bob can then throw out the key bits established while the eavesdropper was listening in,and start over.The first quantum cryptographic ideas were proposed by Stephen Wiesner in the late 1960s,but unfortu-
10 Introduction and overview Figure 1.1. Classically, if we have two very noisy channels of zero capacity running side by side, then the combined channel has zero capacity to send information. Not surprisingly, if we reverse the direction of one of the channels, we still have zero capacity to send information. Quantum mechanically, reversing one of the zero capacity channels can actually allow us to send information! computation involving two or more parties who may not trust one another. The best known cryptographic problem is the transmission of secret messages. Suppose two parties wish to communicate in secret. For example, you may wish to give your credit card number to a merchant in exchange for goods, hopefully without any malevolent third party intercepting your credit card number. The way this is done is to use a cryptographic protocol. We’ll describe in detail how cryptographic protocols work later in the book, but for now it will suffice to make a few simple distinctions. The most important distinction is between private key cryptosystems and public key cryptosystems. The way a private key cryptosystem works is that two parties, ‘Alice’ and ‘Bob’, wish to communicate by sharing a private key, which only they know. The exact form of the key doesn’t matter at this point – think of a string of zeroes and ones. The point is that this key is used by Alice to encrypt the information she wishes to send to Bob. After Alice encrypts she sends the encrypted information to Bob, who must now recover the original information. Exactly how Alice encrypts the message depends upon the private key, so that to recover the original message Bob needs to know the private key, in order to undo the transformation Alice applied. Unfortunately, private key cryptosystems have some severe problems in many contexts. The most basic problem is how to distribute the keys? In many ways, the key distribution problem is just as difficult as the original problem of communicating in private – a malevolent third party may be eavesdropping on the key distribution, and then use the intercepted key to decrypt some of the message transmission. One of the earliest discoveries in quantum computation and quantum information was that quantum mechanics can be used to do key distribution in such a way that Alice and Bob’s security can not be compromised. This procedure is known as quantum cryptography or quantum key distribution. The basic idea is to exploit the quantum mechanical principle that observation in general disturbs the system being observed. Thus, if there is an eavesdropper listening in as Alice and Bob attempt to transmit their key, the presence of the eavesdropper will be visible as a disturbance of the communications channel Alice and Bob are using to establish the key. Alice and Bob can then throw out the key bits established while the eavesdropper was listening in, and start over. The first quantum cryptographic ideas were proposed by Stephen Wiesner in the late 1960s, but unfortu-
Global perspectives 11 nately were not accepted for publication!In 1984 Charles Bennett and Gilles Brassard, building on Wiesner's earlier work,proposed a protocol using quantum mechanics to distribute keys between Alice and Bob,without any possibility of a compromise.Since then numerous quantum cryptographic protocols have been proposed,and experimental prototypes developed.At the time of this writing,the experimental prototypes are nearing the stage where they may be useful in limited-scale real-world applications. The second major type of cryptosystem is the public key cryptosystem.Public key cryptosystems don't rely on Alice and Bob sharing a secret key in advance.Instead,Bob simply publishes a public key',which is made available to the general public.Alice can make use of this public key to encrypt a message which she sends to Bob.What is interesting is that a third party cannot use Bob's public key to decrypt the message! Strictly speaking,we shouldn't say cannot.Rather,the encryption transformation is chosen in a very clever and non-trivial way so that it is extremely difficult (though not impossible)to invert,given only knowledge of the public key.To make inversion easy,Bob has a secret key matched to his public key,which together enable him to easily perform the decryption.This secret key is not known to anybody other than Bob,who can therefore be confident that only he can read the contents of Alice's transmission,to the extent that it is unlikely that anybody else has the computational power to invert the encryption, given only the public key.Public key cryptosystems solve the key distribution problem by making it unnecessary for Alice and Bob to share a private key before communicating. Rather remarkably,public key cryptography did not achieve widespread use until the mid-1970s,when it was proposed independently by Whitfield Diffie and Martin Hellman, and by Ralph Merkle,revolutionizing the field of cryptography.A little later,Ronald Rivest,Adi Shamir,and Leonard Adleman developed the RSA cryptosystem,which at the time of writing is the most widely deployed public key cryptosystem,believed to offer a fine balance of security and practical usability.In 1997 it was disclosed that these ideas-public key cryptography,the Diffie-Hellman and RSA cryptosystems-were actually invented in the late 1960s and early 1970s by researchers working at the British intelligence agency GCHQ. The key to the security of public key cryptosystems is that it should be difficult to invert the encryption stage if only the public key is available.For example,it turns out that inverting the encryption stage of RSA is a problem closely related to factoring. Much of the presumed security of RSA comes from the belief that factoring is a problem hard to solve on a classical computer.However,Shor's fast algorithm for factoring on a quantum computer could be used to break RSA!Similarly,there are other public key cryptosystems which can be broken if a fast algorithm for solving the discrete logarithm problem-like Shor's quantum algorithm for discrete logarithm-were known.This practical application of quantum computers to the breaking of cryptographic codes has excited much of the interest in quantum computation and quantum information We have been looking at the historical antecedents for quantum computation and quantum information.Of course,as the field has grown and matured,it has sprouted its own subfields of research,whose antecedents lie mainly within quantum computation and quantum information. Perhaps the most striking of these is the study of quantum entanglement.Entangle- ment is a uniquely quantum mechanical resource that plays a key role in many of the most interesting applications of quantum computation and quantum information;en- tanglement is iron to the classical world's bronze age.In recent years there has been a
Global perspectives 11 nately were not accepted for publication! In 1984 Charles Bennett and Gilles Brassard, building on Wiesner’s earlier work, proposed a protocol using quantum mechanics to distribute keys between Alice and Bob, without any possibility of a compromise. Since then numerous quantum cryptographic protocols have been proposed, and experimental prototypes developed. At the time of this writing, the experimental prototypes are nearing the stage where they may be useful in limited-scale real-world applications. The second major type of cryptosystem is the public key cryptosystem. Public key cryptosystems don’t rely on Alice and Bob sharing a secret key in advance. Instead, Bob simply publishes a ‘public key’, which is made available to the general public. Alice can make use of this public key to encrypt a message which she sends to Bob. What is interesting is that a third party cannot use Bob’s public key to decrypt the message! Strictly speaking, we shouldn’t say cannot. Rather, the encryption transformation is chosen in a very clever and non-trivial way so that it is extremely difficult (though not impossible) to invert, given only knowledge of the public key. To make inversion easy, Bob has a secret key matched to his public key, which together enable him to easily perform the decryption. This secret key is not known to anybody other than Bob, who can therefore be confident that only he can read the contents of Alice’s transmission, to the extent that it is unlikely that anybody else has the computational power to invert the encryption, given only the public key. Public key cryptosystems solve the key distribution problem by making it unnecessary for Alice and Bob to share a private key before communicating. Rather remarkably, public key cryptography did not achieve widespread use until the mid-1970s, when it was proposed independently by Whitfield Diffie and Martin Hellman, and by Ralph Merkle, revolutionizing the field of cryptography. A little later, Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA cryptosystem, which at the time of writing is the most widely deployed public key cryptosystem, believed to offer a fine balance of security and practical usability. In 1997 it was disclosed that these ideas – public key cryptography, the Diffie–Hellman and RSA cryptosystems – were actually invented in the late 1960s and early 1970s by researchers working at the British intelligence agency GCHQ. The key to the security of public key cryptosystems is that it should be difficult to invert the encryption stage if only the public key is available. For example, it turns out that inverting the encryption stage of RSA is a problem closely related to factoring. Much of the presumed security of RSA comes from the belief that factoring is a problem hard to solve on a classical computer. However, Shor’s fast algorithm for factoring on a quantum computer could be used to break RSA! Similarly, there are other public key cryptosystems which can be broken if a fast algorithm for solving the discrete logarithm problem – like Shor’s quantum algorithm for discrete logarithm – were known. This practical application of quantum computers to the breaking of cryptographic codes has excited much of the interest in quantum computation and quantum information. We have been looking at the historical antecedents for quantum computation and quantum information. Of course, as the field has grown and matured, it has sprouted its own subfields of research, whose antecedents lie mainly within quantum computation and quantum information. Perhaps the most striking of these is the study of quantum entanglement. Entanglement is a uniquely quantum mechanical resource that plays a key role in many of the most interesting applications of quantum computation and quantum information; entanglement is iron to the classical world’s bronze age. In recent years there has been a
12 Introduction and overview tremendous effort trying to better understand the properties of entanglement considered as a fundamental resource of Nature,of comparable importance to energy,information, entropy,or any other fundamental resource.Although there is as yet no complete theory of entanglement,some progress has been made in understanding this strange property of quantum mechanics.It is hoped by many researchers that further study of the properties of entanglement will yield insights that facilitate the development of new applications in quantum computation and quantum information. 1.1.2 Future directions We've looked at some of the history and present status of quantum computation and quantum information.What of the future?What can quantum computation and quan- tum information offer to science,to technology,and to humanity?What benefits does quantum computation and quantum information confer upon its parent fields of computer science,information theory,and physics?What are the key open problems of quantum computation and quantum information?We will make a few very brief remarks about these overarching questions before moving onto more detailed investigations. Quantum computation and quantum information has taught us to think physically about computation,and we have discovered that this approach yields many new and exciting capabilities for information processing and communication.Computer scientists and information theorists have been gifted with a new and rich paradigm for explo- ration.Indeed,in the broadest terms we have learned that any physical theory,not just quantum mechanics,may be used as the basis for a theory of information processing and communication.The fruits of these explorations may one day result in information processing devices with capabilities far beyond today's computing and communications systems,with concomitant benefits and drawbacks for society as a whole. Quantum computation and quantum information certainly offer challenges aplenty to physicists,but it is perhaps a little subtle what quantum computation and quantum information offers to physics in the long term.We believe that just as we have learned to think physically about computation,we can also learn to think computationally about physics.Whereas physics has traditionally been a discipline focused on understanding 'elementary'objects and simple systems,many interesting aspects of Nature arise only when things become larger and more complicated.Chemistry and engineering deal with such complexity to some extent,but most often in a rather ad hoc fashion.One of the messages of quantum computation and information is that new tools are available for traversing the gulf between the small and the relatively complex:computation and algorithms provide systematic means for constructing and understanding such systems. Applying ideas from these fields is already beginning to yield new insights into physics. It is our hope that this perspective will blossom in years to come into a fruitful way of understanding all aspects of physics. We've briefly examined some of the key motivations and ideas underlying quantum computation and quantum information.Over the remaining sections of this chapter we give a more technical but still accessible introduction to these motivations and ideas,with the hope of giving you a bird's-eye view of the field as it is presently poised
12 Introduction and overview tremendous effort trying to better understand the properties of entanglement considered as a fundamental resource of Nature, of comparable importance to energy, information, entropy, or any other fundamental resource. Although there is as yet no complete theory of entanglement, some progress has been made in understanding this strange property of quantum mechanics. It is hoped by many researchers that further study of the properties of entanglement will yield insights that facilitate the development of new applications in quantum computation and quantum information. 1.1.2 Future directions We’ve looked at some of the history and present status of quantum computation and quantum information. What of the future? What can quantum computation and quantum information offer to science, to technology, and to humanity? What benefits does quantum computation and quantum information confer upon its parent fields of computer science, information theory, and physics? What are the key open problems of quantum computation and quantum information? We will make a few very brief remarks about these overarching questions before moving onto more detailed investigations. Quantum computation and quantum information has taught us to think physically about computation, and we have discovered that this approach yields many new and exciting capabilities for information processing and communication. Computer scientists and information theorists have been gifted with a new and rich paradigm for exploration. Indeed, in the broadest terms we have learned that any physical theory, not just quantum mechanics, may be used as the basis for a theory of information processing and communication. The fruits of these explorations may one day result in information processing devices with capabilities far beyond today’s computing and communications systems, with concomitant benefits and drawbacks for society as a whole. Quantum computation and quantum information certainly offer challenges aplenty to physicists, but it is perhaps a little subtle what quantum computation and quantum information offers to physics in the long term. We believe that just as we have learned to think physically about computation, we can also learn to think computationally about physics. Whereas physics has traditionally been a discipline focused on understanding ‘elementary’ objects and simple systems, many interesting aspects of Nature arise only when things become larger and more complicated. Chemistry and engineering deal with such complexity to some extent, but most often in a rather ad hoc fashion. One of the messages of quantum computation and information is that new tools are available for traversing the gulf between the small and the relatively complex: computation and algorithms provide systematic means for constructing and understanding such systems. Applying ideas from these fields is already beginning to yield new insights into physics. It is our hope that this perspective will blossom in years to come into a fruitful way of understanding all aspects of physics. We’ve briefly examined some of the key motivations and ideas underlying quantum computation and quantum information. Over the remaining sections of this chapter we give a more technical but still accessible introduction to these motivations and ideas, with the hope of giving you a bird’s-eye view of the field as it is presently poised
Ouantum bits 13 1.2 Quantum bits The bit is the fundamental concept of classical computation and classical information. Quantum computation and quantum information are built upon an analogous concept, the quantum bit,or qubit for short.In this section we introduce the properties of single and multiple qubits,comparing and contrasting their properties to those of classical bits. What is a qubit?We're going to describe qubits as mathematical objects with certain specific properties.'But hang on',you say,I thought qubits were physical objects.'It's true that qubits,like bits,are realized as actual physical systems,and in Section 1.5 and Chapter 7 we describe in detail how this connection between the abstract mathematical point of view and real systems is made.However,for the most part we treat qubits as abstract mathematical objects.The beauty of treating qubits as abstract entities is that it gives us the freedom to construct a general theory of quantum computation and quantum information which does not depend upon a specific system for its realization. What then is a qubit?Just as a classical bit has a state-either 0 or 1-a qubit also has a state.Two possible states for a qubit are the states 0)and |1),which as you might guess correspond to the states 0 and 1 for a classical bit.Notation like')'is called the Dirac notation,and we'll be seeing it often,as it's the standard notation for states in quantum mechanics.The difference between bits and qubits is that a qubit can be in a state other than 0)or 1).It is also possible to form linear combinations of states,often called superpositions: 1)=a10)+311) (1.1) The numbers a and B are complex numbers,although for many purposes not much is lost by thinking of them as real numbers.Put another way,the state of a qubit is a vector in a two-dimensional complex vector space.The special states 0)and |1)are known as computational basis states,and form an orthonormal basis for this vector space. We can examine a bit to determine whether it is in the state 0 or 1.For example, computers do this all the time when they retrieve the contents of their memory.Rather remarkably,we cannot examine a qubit to determine its quantum state,that is,the values of o and B.Instead,quantum mechanics tells us that we can only acquire much more restricted information about the quantum state.When we measure a qubit we get either the result 0,with probability a2,or the result 1,with probability Naturally, a2+2=1,since the probabilities must sum to one.Geometrically,we can interpret this as the condition that the qubit's state be normalized to length 1.Thus,in general a qubit's state is a unit vector in a two-dimensional complex vector space. This dichotomy between the unobservable state of a qubit and the observations we can make lies at the heart of quantum computation and quantum information.In most of our abstract models of the world,there is a direct correspondence between elements of the abstraction and the real world,just as an architect's plans for a building are in correspondence with the final building.The lack of this direct correspondence in quantum mechanics makes it difficult to intuit the behavior of quantum systems;however,there is an indirect correspondence,for qubit states can be manipulated and transformed in ways which lead to measurement outcomes which depend distinctly on the different properties of the state.Thus,these quantum states have real,experimentally verifiable consequences,which we shall see are essential to the power of quantum computation and quantum information
Quantum bits 13 1.2 Quantum bits The bit is the fundamental concept of classical computation and classical information. Quantum computation and quantum information are built upon an analogous concept, the quantum bit, or qubit for short. In this section we introduce the properties of single and multiple qubits, comparing and contrasting their properties to those of classical bits. What is a qubit? We’re going to describe qubits as mathematical objects with certain specific properties. ‘But hang on’, you say, ‘I thought qubits were physical objects.’ It’s true that qubits, like bits, are realized as actual physical systems, and in Section 1.5 and Chapter 7 we describe in detail how this connection between the abstract mathematical point of view and real systems is made. However, for the most part we treat qubits as abstract mathematical objects. The beauty of treating qubits as abstract entities is that it gives us the freedom to construct a general theory of quantum computation and quantum information which does not depend upon a specific system for its realization. What then is a qubit? Just as a classical bit has a state – either 0 or 1 – a qubit also has a state. Two possible states for a qubit are the states |0 and |1, which as you might guess correspond to the states 0 and 1 for a classical bit. Notation like ‘| ’ is called the Dirac notation, and we’ll be seeing it often, as it’s the standard notation for states in quantum mechanics. The difference between bits and qubits is that a qubit can be in a state other than |0 or |1. It is also possible to form linear combinations of states, often called superpositions: |ψ = α |0 + β |1. (1.1) The numbers α and β are complex numbers, although for many purposes not much is lost by thinking of them as real numbers. Put another way, the state of a qubit is a vector in a two-dimensional complex vector space. The special states |0 and |1 are known as computational basis states, and form an orthonormal basis for this vector space. We can examine a bit to determine whether it is in the state 0 or 1. For example, computers do this all the time when they retrieve the contents of their memory. Rather remarkably, we cannot examine a qubit to determine its quantum state, that is, the values of α and β. Instead, quantum mechanics tells us that we can only acquire much more restricted information about the quantum state. When we measure a qubit we get either the result 0, with probability |α| 2, or the result 1, with probability |β| 2 . Naturally, |α| 2 + |β| 2 = 1, since the probabilities must sum to one. Geometrically, we can interpret this as the condition that the qubit’s state be normalized to length 1. Thus, in general a qubit’s state is a unit vector in a two-dimensional complex vector space. This dichotomy between the unobservable state of a qubit and the observations we can make lies at the heart of quantum computation and quantum information. In most of our abstract models of the world, there is a direct correspondence between elements of the abstraction and the real world, just as an architect’s plans for a building are in correspondence with the final building. The lack of this direct correspondence in quantum mechanics makes it difficult to intuit the behavior of quantum systems; however, there is an indirect correspondence, for qubit states can be manipulated and transformed in ways which lead to measurement outcomes which depend distinctly on the different properties of the state. Thus, these quantum states have real, experimentally verifiable consequences, which we shall see are essential to the power of quantum computation and quantum information.
14 Introduction and overview The ability of a qubit to be in a superposition state runs counter to our 'common sense' understanding of the physical world around us.A classical bit is like a coin:either heads or tails up.For imperfect coins,there may be intermediate states like having it balanced on an edge,but those can be disregarded in the ideal case.By contrast,a qubit can exist in a continuum of states between 0)and |1)-until it is observed.Let us emphasize again that when a qubit is measured,it only ever gives 0'or '1'as the measurement result-probabilistically.For example,a qubit can be in the state 网+方心， 1 (1.2) which,when measured,gives the result 0 fifty percent (/2)of the time,and the result I fifty percent of the time.We will return often to this state,which is sometimes denoted |+) Despite this strangeness,qubits are decidedly real,their existence and behavior ex- tensively validated by experiments(discussed in Section 1.5 and Chapter 7),and many different physical systems can be used to realize qubits.To get a concrete feel for how a qubit can be realized it may be helpful to list some of the ways this realization may occur: as the two different polarizations of a photon;as the alignment of a nuclear spin in a uniform magnetic field;as two states of an electron orbiting a single atom such as shown in Figure 1.2.In the atom model,the electron can exist in either the so-called 'ground' or 'excited'states,which we'll call 0)and 1),respectively.By shining light on the atom, with appropriate energy and for an appropriate length of time,it is possible to move the electron from the 0)state to the 1)state and vice versa.But more interestingly,by reducing the time we shine the light,an electron initially in the state 0)can be moved halfway'between 0)and |1),into the |+)state. Figure 1.2.Qubit represented by two electronic levels in an atom. Naturally,a great deal of attention has been given to the 'meaning'or 'interpretation' that might be attached to superposition states,and of the inherently probabilistic nature of observations on quantum systems.However,by and large,we shall not concern ourselves with such discussions in this book.Instead,our intent will be to develop mathematical and conceptual pictures which are predictive. One picture useful in thinking about qubits is the following geometric representation
14 Introduction and overview The ability of a qubit to be in a superposition state runs counter to our ‘common sense’ understanding of the physical world around us. A classical bit is like a coin: either heads or tails up. For imperfect coins, there may be intermediate states like having it balanced on an edge, but those can be disregarded in the ideal case. By contrast, a qubit can exist in a continuum of states between |0 and |1 – until it is observed. Let us emphasize again that when a qubit is measured, it only ever gives ‘0’ or ‘1’ as the measurement result – probabilistically. For example, a qubit can be in the state 1 √ 2 |0 + 1 √ 2 |1, (1.2) which, when measured, gives the result 0 fifty percent (|1/ √ 2| 2) of the time, and the result 1 fifty percent of the time. We will return often to this state, which is sometimes denoted |+. Despite this strangeness, qubits are decidedly real, their existence and behavior extensively validated by experiments (discussed in Section 1.5 and Chapter 7), and many different physical systems can be used to realize qubits. To get a concrete feel for how a qubit can be realized it may be helpful to list some of the ways this realization may occur: as the two different polarizations of a photon; as the alignment of a nuclear spin in a uniform magnetic field; as two states of an electron orbiting a single atom such as shown in Figure 1.2. In the atom model, the electron can exist in either the so-called ‘ground’ or ‘excited’ states, which we’ll call |0 and |1, respectively. By shining light on the atom, with appropriate energy and for an appropriate length of time, it is possible to move the electron from the |0 state to the |1 state and vice versa. But more interestingly, by reducing the time we shine the light, an electron initially in the state |0 can be moved ‘halfway’ between |0 and |1, into the |+ state. Figure 1.2. Qubit represented by two electronic levels in an atom. Naturally, a great deal of attention has been given to the ‘meaning’ or ‘interpretation’ that might be attached to superposition states, and of the inherently probabilistic nature of observations on quantum systems. However, by and large, we shall not concern ourselves with such discussions in this book. Instead, our intent will be to develop mathematical and conceptual pictures which are predictive. One picture useful in thinking about qubits is the following geometric representation.