Afterword to the Tenth Anniversary Edition An enormous amount has happened in quantum information science in the 10 years since the first edition of this book,and in this afterword we cannot summarize even a tiny fraction of that work.But a few especially striking developments merit comment,and may perhaps whet your appetite for more. Perhaps the most impressive progress has been in the area of experimental implemen- tation.While we are still many years from building large-scale quantum computers,much progress has been made.Superconducting circuits have been used to implement simple two-qubit quantum algorithms,and three-qubit systems are nearly within reach.Qubits based on nuclear spins and single photons have been used,respectively,to demonstrate proof-of-principle for simple forms of quantum error correction and quantum simulation. But the most impressive progress of all has been made with trapped ion systems,which have been used to implement many two-and three-qubit algorithms and algorithmic building blocks,including the quantum search algorithm and the quantum Fourier trans- form.Trapped ions have also been used to demonstrate basic quantum communication primitives,including quantum error correction and quantum teleportation. A second area of progress has been in understanding what physical resources are required to quantum compute.Perhaps the most intriguing breakthrough here has been the discovery that quantum computation can be done via measurement alone.For many years, the conventional wisdom was that coherent superposition-preserving unitary dynamics was an essential part of the power of quantum computers.This conventional wisdom was blown away by the realization that quantum computation can be done without any unitary dynamics at all.Instead,in some new models of quantum computation,quantum measurements alone can be used to do arbitrary quantum computations.The only coherent resource in these models is quantum memory,i.e.,theability to store quantum information. An especially interesting example of these models is the one-way quantum computer,or cluster-state computer.To quantum compute in the cluster-state model requires only that the experimenter have possession of a fixed universal state known as the cluster state. With a cluster state in hand,quantum computation can be implemented simply by doing a sequence of single-qubit measurements,with the particular computation done being determined by which qubits are measured,when they are measured,and how they are measured.This is remarkable:you're given a fixed quantum state,and then quantum compute by "looking"at the individual qubits in appropriate ways. A third area of progress has been in classically simulating quantum systems.Feynman's pioneering 1982 paper on quantum computing was motivated in part by the observation that quantum systems often seem hard to simulate on conventional classical computers. Of course,at the time there was only a limited understanding of how difficult it is to simulate different quantum systems on ordinary classical computers.But in the 1990s and,especially,in the 2000s,we have learned much about which quantum systems are easy
Afterword to the Tenth Anniversary Edition An enormous amount has happened in quantum information science in the 10 years since the first edition of this book, and in this afterword we cannot summarize even a tiny fraction of that work. But a few especially striking developments merit comment, and may perhaps whet your appetite for more. Perhaps the most impressive progress has been in the area of experimental implementation. While we are still many years from building large-scale quantum computers, much progress has been made. Superconducting circuits have been used to implement simple two-qubit quantum algorithms, and three-qubit systems are nearly within reach. Qubits based on nuclear spins and single photons have been used, respectively, to demonstrate proof-of-principle for simple forms of quantum error correction and quantum simulation. But the most impressive progress of all has been made with trapped ion systems, which have been used to implement many two- and three-qubit algorithms and algorithmic building blocks, including the quantum search algorithm and the quantum Fourier transform. Trapped ions have also been used to demonstrate basic quantum communication primitives, including quantum error correction and quantum teleportation. A second area of progress has been in understanding what physical resources are required to quantum compute. Perhaps the most intriguing breakthrough here has been the discovery that quantum computation can be done via measurement alone. For many years, the conventional wisdom was that coherent superposition-preserving unitary dynamics was an essential part of the power of quantum computers. This conventional wisdom was blown away by the realization that quantum computation can be done without any unitary dynamics at all. Instead, in some new models of quantum computation, quantum measurements alone can be used to do arbitrary quantum computations. The only coherent resource in these models is quantum memory, i.e., the ability to store quantum information. An especially interesting example of these models is the one-way quantum computer, or cluster-state computer. To quantum compute in the cluster-state model requires only that the experimenter have possession of a fixed universal state known as the cluster state. With a cluster state in hand, quantum computation can be implemented simply by doing a sequence of single-qubit measurements, with the particular computation done being determined by which qubits are measured, when they are measured, and how they are measured. This is remarkable: you’re given a fixed quantum state, and then quantum compute by “looking” at the individual qubits in appropriate ways. A third area of progress has been in classically simulating quantum systems. Feynman’s pioneering 1982 paper on quantum computing was motivated in part by the observation that quantum systems often seem hard to simulate on conventional classical computers. Of course, at the time there was only a limited understanding of how difficult it is to simulate different quantum systems on ordinary classical computers. But in the 1990s and, especially, in the 2000s, we have learned much about which quantum systems are easy
XX Afterword to the Tenth Anniversary Edition to simulate,and which are hard.Ingenious algorithms have been developed to classically simulate many quantum systems that were formerly thought to be hard to simulate,in particular,many quantum systems in one spatial dimension,and certain two-dimensional quantum systems.These classical algorithms have been made possible by the development of insightful classical descriptions that capture in a compact way much or all of the essential physics of the system in question.At the same time,we have learned that some systems that formerly seemed simple are surprisingly complex.For example,it has long been known that quantum systems based on a certain type of optical component-what are called linear optical systems-are easily simulated classically.So it was surprising when it was discovered that adding two seemingly innocuous components-single-photon sources and photodetectors-gave linear optics the full power of quantum computation.These and similar investigations have deepened our understanding of which quantum systems are easy to simulate,which quantum systems are hard to simulate,and why. A fourth area of progress has been a greatly deepened understanding of quantum communication channels.A beautiful and complete theory has been developed of how entangled quantum states can assist classical communication over quantum channels.A plethora of different quantum protocols for communication have been organized into a comprehensive family(headed by“mother'”and“father'”protocols),unifying much of our understanding of the different types of communication possible with quantum information.A sign of the progress is the disproof of one of the key unsolved conjectures reported in this book(p.554),namely,that the communication capacity of a quantum channel with product states is equal to the unconstrained capacity(i.e.,the capacity with any entangled state allowed as input).But,despite the progress,much remains beyond our understanding.Only very recently,for example,it was discovered,to considerable surprise,that two quantum channels,each with zero quantum capacity,can have a positive quantum capacity when used together;the analogous result,with classical capacities over classical channels,is known to be impossible. One of the main motivations for work in quantum information science is the prospect of fast quantum algorithms to solve important computational problems.Here,the progress over the past decade has been mixed.Despite great ingenuity and effort,the chief algo- rithmic insights stand as they were 10 years ago.There has been considerable technical progress,but we do not yet understand what exactly it is that makes quantum comput- ers powerful,or on what class of problems they can be expected to outperform classical computers. What is exciting,though,is that ideas from quantum computation have been used to prove a variety of theorems about classical computation.These have included,for example,results about the difficulty of finding certain hidden vectors in a discrete lattice of points.The striking feature is that these proofs,utilizing ideas of quantum computation, are sometimes considerably simpler and more elegant than prior,classical proofs.Thus, an awareness has grown that quantum computation may be a more natural model of computation than the classical model,and perhaps fundamental results may be more easily revealed through the ideas of quantum computation
xx Afterword to the Tenth Anniversary Edition to simulate, and which are hard. Ingenious algorithms have been developed to classically simulate many quantum systems that were formerly thought to be hard to simulate, in particular, many quantum systems in one spatial dimension, and certain two-dimensional quantum systems. These classical algorithms have been made possible by the development of insightful classical descriptions that capture in a compact way much or all of the essential physics of the system in question. At the same time, we have learned that some systems that formerly seemed simple are surprisingly complex. For example, it has long been known that quantum systems based on a certain type of optical component – what are called linear optical systems – are easily simulated classically. So it was surprising when it was discovered that adding two seemingly innocuous components – single-photon sources and photodetectors – gave linear optics the full power of quantum computation. These and similar investigations have deepened our understanding of which quantum systems are easy to simulate, which quantum systems are hard to simulate, and why. A fourth area of progress has been a greatly deepened understanding of quantum communication channels. A beautiful and complete theory has been developed of how entangled quantum states can assist classical communication over quantum channels. A plethora of different quantum protocols for communication have been organized into a comprehensive family (headed by “mother” and “father” protocols), unifying much of our understanding of the different types of communication possible with quantum information. A sign of the progress is the disproof of one of the key unsolved conjectures reported in this book (p. 554), namely, that the communication capacity of a quantum channel with product states is equal to the unconstrained capacity (i.e., the capacity with any entangled state allowed as input). But, despite the progress, much remains beyond our understanding. Only very recently, for example, it was discovered, to considerable surprise, that two quantum channels, each with zero quantum capacity, can have a positive quantum capacity when used together; the analogous result, with classical capacities over classical channels, is known to be impossible. One of the main motivations for work in quantum information science is the prospect of fast quantum algorithms to solve important computational problems. Here, the progress over the past decade has been mixed. Despite great ingenuity and effort, the chief algorithmic insights stand as they were 10 years ago. There has been considerable technical progress, but we do not yet understand what exactly it is that makes quantum computers powerful, or on what class of problems they can be expected to outperform classical computers. What is exciting, though, is that ideas from quantum computation have been used to prove a variety of theorems about classical computation. These have included, for example, results about the difficulty of finding certain hidden vectors in a discrete lattice of points. The striking feature is that these proofs, utilizing ideas of quantum computation, are sometimes considerably simpler and more elegant than prior, classical proofs. Thus, an awareness has grown that quantum computation may be a more natural model of computation than the classical model, and perhaps fundamental results may be more easily revealed through the ideas of quantum computation
Preface This book provides an introduction to the main ideas and techniques of the field of quantum computation and quantum information.The rapid rate of progress in this field and its cross-disciplinary nature have made it difficult for newcomers to obtain a broad overview of the most important techniques and results of the field. Our purpose in this book is therefore twofold.First,we introduce the background material in computer science,mathematics and physics necessary to understand quan- tum computation and quantum information.This is done at a level comprehensible to readers with a background at least the equal of a beginning graduate student in one or more of these three disciplines;the most important requirements are a certain level of mathematical maturity,and the desire to learn about quantum computation and quantum information.The second purpose of the book is to develop in detail the central results of quantum computation and quantum information.With thorough study the reader should develop a working understanding of the fundamental tools and results of this exciting field,either as part of their general education,or as a prelude to independent research in quantum computation and quantum information. Structure of the book The basic structure of the book is depicted in Figure 1.The book is divided into three parts.The general strategy is to proceed from the concrete to the more abstract whenever possible.Thus we study quantum computation before quantum information;specific quantum error-correcting codes before the more general results of quantum information theory;and throughout the book try to introduce examples before developing general theory. Part I provides a broad overview of the main ideas and results of the field of quan- tum computation and quantum information,and develops the background material in computer science,mathematics and physics necessary to understand quantum compu- tation and quantum information in depth.Chapter I is an introductory chapter which outlines the historical development and fundamental concepts of the field,highlighting some important open problems along the way.The material has been structured so as to be accessible even without a background in computer science or physics.The back- ground material needed for a more detailed understanding is developed in Chapters 2 and 3,which treat in depth the fundamental notions of quantum mechanics and com- puter science,respectively.You may elect to concentrate more or less heavily on different chapters of Part I,depending upon your background,returning later as necessary to fill any gaps in your knowledge of the fundamentals of quantum mechanics and computer science. Part II describes quantum computation in detail.Chapter 4 describes the fundamen-
Preface This book provides an introduction to the main ideas and techniques of the field of quantum computation and quantum information. The rapid rate of progress in this field and its cross-disciplinary nature have made it difficult for newcomers to obtain a broad overview of the most important techniques and results of the field. Our purpose in this book is therefore twofold. First, we introduce the background material in computer science, mathematics and physics necessary to understand quantum computation and quantum information. This is done at a level comprehensible to readers with a background at least the equal of a beginning graduate student in one or more of these three disciplines; the most important requirements are a certain level of mathematical maturity, and the desire to learn about quantum computation and quantum information. The second purpose of the book is to develop in detail the central results of quantum computation and quantum information. With thorough study the reader should develop a working understanding of the fundamental tools and results of this exciting field, either as part of their general education, or as a prelude to independent research in quantum computation and quantum information. Structure of the book The basic structure of the book is depicted in Figure 1. The book is divided into three parts. The general strategy is to proceed from the concrete to the more abstract whenever possible. Thus we study quantum computation before quantum information; specific quantum error-correcting codes before the more general results of quantum information theory; and throughout the book try to introduce examples before developing general theory. Part I provides a broad overview of the main ideas and results of the field of quantum computation and quantum information, and develops the background material in computer science, mathematics and physics necessary to understand quantum computation and quantum information in depth. Chapter 1 is an introductory chapter which outlines the historical development and fundamental concepts of the field, highlighting some important open problems along the way. The material has been structured so as to be accessible even without a background in computer science or physics. The background material needed for a more detailed understanding is developed in Chapters 2 and 3, which treat in depth the fundamental notions of quantum mechanics and computer science, respectively. You may elect to concentrate more or less heavily on different chapters of Part I, depending upon your background, returning later as necessary to fill any gaps in your knowledge of the fundamentals of quantum mechanics and computer science. Part II describes quantum computation in detail. Chapter 4 describes the fundamen-
xxii Preface PatL☐ Fundamental Concepts Introduction Quantum and Overview [1 2 Computer Mechanics Science 3 Part Il Part llⅢ Quantum Quantum Computation Information Quantum Noise and 4 Quantum Operations e Distance Circuits Measures Quantum Fourier Transform Quantum Quantum 10 Error-Correction Entropy 11 Search Physical Quantum Information Realizations 12 Theory Figure 1.Structure of the book. tal elements needed to perform quantum computation,and presents many elementary operations which may be used to develop more sophisticated applications of quantum computation.Chapters 5 and 6 describe the quantum Fourier transform and the quantum search algorithm,the two fundamental quantum algorithms presently known.Chapter 5 also explains how the quantum Fourier transform may be used to solve the factoring and discrete logarithm problems,and the importance of these results to cryptography.Chap- ter 7 describes general design principles and criteria for good physical implementations of quantum computers,using as examples several realizations which have been successfully demonstrated in the laboratory. Part III is about quantum information:what it is,how information is represented and communicated using quantum states,and how to describe and deal with the corruption of quantum and classical information.Chapter 8 describes the properties of quantum noise which are needed to understand real-world quantum information processing,and the quantum operations formalism,a powerful mathematical tool for understanding quan- tum noise.Chapter 9 describes distance measures for quantum information which allow us to make quantitatively precise what it means to say that two items of quantum infor- mation are similar.Chapter 10 explains quantum error-correcting codes,which may be used to protect quantum computations against the effect of noise.An important result in this chapter is the threshold theorem,which shows that for realistic noise models,noise is in principle not a serious impediment to quantum computation.Chapter 11 introduces the fundamental information-theoretic concept of entropy,explaining many properties of entropy in both classical and quantum information theory.Finally,Chapter 12 discusses the information carrying properties of quantum states and quantum communication chan-
Preface ! " # " Figure 1. Structure of the book. tal elements needed to perform quantum computation, and presents many elementary operations which may be used to develop more sophisticated applications of quantum computation. Chapters 5 and 6 describe the quantum Fourier transform and the quantum search algorithm, the two fundamental quantum algorithms presently known. Chapter 5 also explains how the quantum Fourier transform may be used to solve the factoring and discrete logarithm problems, and the importance of these results to cryptography. Chapter 7 describes general design principles and criteria for good physical implementations of quantum computers, using as examples several realizations which have been successfully demonstrated in the laboratory. Part III is about quantum information: what it is, how information is represented and communicated using quantum states, and how to describe and deal with the corruption of quantum and classical information. Chapter 8 describes the properties of quantum noise which are needed to understand real-world quantum information processing, and the quantum operations formalism, a powerful mathematical tool for understanding quantum noise. Chapter 9 describes distance measures for quantum information which allow us to make quantitatively precise what it means to say that two items of quantum information are similar. Chapter 10 explains quantum error-correcting codes, which may be used to protect quantum computations against the effect of noise. An important result in this chapter is the threshold theorem, which shows that for realistic noise models, noise is in principle not a serious impediment to quantum computation. Chapter 11 introduces the fundamental information-theoretic concept of entropy, explaining many properties of entropy in both classical and quantum information theory. Finally, Chapter 12 discusses the information carrying properties of quantum states and quantum communication chanxxii
Preface xxiii nels,detailing many of the strange and interesting properties such systems can have for the transmission of information both classical and quantum,and for the transmission of secret information. A large number of exercises and problems appear throughout the book.Exercises are intended to solidify understanding of basic material and appear within the main body of the text.With few exceptions these should be easily solved with a few minutes work. Problems appear at the end of each chapter,and are intended to introduce you to new and interesting material for which there was not enough space in the main text.Often the problems are in multiple parts,intended to develop a particular line of thought in some depth.A few of the problems were unsolved as the book went to press.When this is the case it is noted in the statement of the problem.Each chapter concludes with a summary of the main results of the chapter,and with a'History and further reading'section that charts the development of the main ideas in the chapter,giving citations and references for the whole chapter,as well as providing recommendations for further reading. The front matter of the book contains a detailed Table of Contents,which we encourage you to browse.There is also a guide to nomenclature and notation to assist you as you read. The end matter of the book contains six appendices,a bibliography,and an index. Appendix I reviews some basic definitions,notations,and results in elementary prob- ability theory.This material is assumed to be familiar to readers,and is included for ease of reference.Similarly,Apendix 2 reviews some elementary concepts from group theory, and is included mainly for convenience.Appendix 3 contains a proof of the Solovay- Kitaev theorem,an important result for quantum computation,which shows that a finite set of quantum gates can be used to quickly approximate an arbitrary quantum gate. Appendix 4 reviews the elementary material on number theory needed to understand the quantum algorithms for factoring and discrete logarithm,and the RSA cryptosystem, which is itself reviewed in Appendix 5.Appendix 6 contains a proof of Lieb's theorem, one of the most important results in quantum computation and quantum information, and a precursor to important entropy inequalities such as the celebrated strong subad- ditivity inequality.The proofs of the Solovay-Kitaey theorem and Lieb's theorem are lengthy enough that we felt they justified a treatment apart from the main text. The bibliography contains a listing of all reference materials cited in the text of the book.Our apologies to any researcher whose work we have inadvertently omitted from citation. The field of quantum computation and quantum information has grown so rapidly in recent years that we have not been able to cover all topics in as much depth as we would have liked.Three topics deserve special mention.The first is the subject of entanglement measures.As we explain in the book,entanglement is a key element in effects such as quantum teleportation,fast quantum algorithms,and quantum error-correction.It is, in short,a resource of great utility in quantum computation and quantum information. There is a thriving research community currently fleshing out the notion of entanglement as a new type of physical resource,finding principles which govern its manipulation and utilization.We felt that these investigations,while enormously promising,are not yet complete enough to warrant the more extensive coverage we have given to other subjects in this book,and we restrict ourselves to a brief taste in Chapter 12.Similarly,the sub- ject of distributed quantum computation(sometimes known as quantum communication complexity)is an enormously promising subject under such active development that we
Preface nels, detailing many of the strange and interesting properties such systems can have for the transmission of information both classical and quantum, and for the transmission of secret information. A large number of exercises and problems appear throughout the book. Exercises are intended to solidify understanding of basic material and appear within the main body of the text. With few exceptions these should be easily solved with a few minutes work. Problems appear at the end of each chapter, and are intended to introduce you to new and interesting material for which there was not enough space in the main text. Often the problems are in multiple parts, intended to develop a particular line of thought in some depth. A few of the problems were unsolved as the book went to press. When this is the case it is noted in the statement of the problem. Each chapter concludes with a summary of the main results of the chapter, and with a ‘History and further reading’ section that charts the development of the main ideas in the chapter, giving citations and references for the whole chapter, as well as providing recommendations for further reading. The front matter of the book contains a detailed Table of Contents, which we encourage you to browse. There is also a guide to nomenclature and notation to assist you as you read. The end matter of the book contains six appendices, a bibliography, and an index. Appendix 1 reviews some basic definitions, notations, and results in elementary probability theory. This material is assumed to be familiar to readers, and is included for ease of reference. Similarly, Apendix 2 reviews some elementary concepts from group theory, and is included mainly for convenience. Appendix 3 contains a proof of the Solovay– Kitaev theorem, an important result for quantum computation, which shows that a finite set of quantum gates can be used to quickly approximate an arbitrary quantum gate. Appendix 4 reviews the elementary material on number theory needed to understand the quantum algorithms for factoring and discrete logarithm, and the RSA cryptosystem, which is itself reviewed in Appendix 5. Appendix 6 contains a proof of Lieb’s theorem, one of the most important results in quantum computation and quantum information, and a precursor to important entropy inequalities such as the celebrated strong subadditivity inequality. The proofs of the Solovay–Kitaev theorem and Lieb’s theorem are lengthy enough that we felt they justified a treatment apart from the main text. The bibliography contains a listing of all reference materials cited in the text of the book. Our apologies to any researcher whose work we have inadvertently omitted from citation. The field of quantum computation and quantum information has grown so rapidly in recent years that we have not been able to cover all topics in as much depth as we would have liked. Three topics deserve special mention. The first is the subject of entanglement measures. As we explain in the book, entanglement is a key element in effects such as quantum teleportation, fast quantum algorithms, and quantum error-correction. It is, in short, a resource of great utility in quantum computation and quantum information. There is a thriving research community currently fleshing out the notion of entanglement as a new type of physical resource, finding principles which govern its manipulation and utilization. We felt that these investigations, while enormously promising, are not yet complete enough to warrant the more extensive coverage we have given to other subjects in this book, and we restrict ourselves to a brief taste in Chapter 12. Similarly, the subject of distributed quantum computation (sometimes known as quantum communication complexity) is an enormously promising subject under such active development that we xxiii