xxiV Preface have not given it a treatment for fear of being obsolete before publication of the book The implementation of quantum information processing machines has also developed into a fascinating and rich area,and we limit ourselves to but a single chapter on this subject.Clearly,much more can be said about physical implementations,but this would begin to involve many more areas of physics,chemistry,and engineering,which we do not have room for here. How to use this book This book may be used in a wide variety of ways.It can be used as the basis for a variety of courses,from short lecture courses on a specific topic in quantum computation and quantum information,through to full-year classes covering the entire field.It can be used for independent study by people who would like to learn just a little about quantum computation and quantum information,or by people who would like to be brought up to the research frontier.It is also intended to act as a reference work for current researchers in the field.We hope that it will be found especially valuable as an introduction for researchers new to the field. Note to the independent reader The book is designed to be accessible to the independent reader.A large number of exer- cises are peppered throughout the text,which can be used as self-tests for understanding of the material in the main text.The Table of Contents and end of chapter summaries should enable you to quickly determine which chapters you wish to study in most depth. The dependency diagram,Figure 1,will help you determine in what order material in the book may be covered. Note to the teacher This book covers a diverse range of topics,and can therefore be used as the basis for a wide variety of courses. A one-semester course on quantum computation could be based upon a selection of material from Chapters 1 through 3,depending on the background of the class,followed by Chapter 4 on quantum circuits,Chapters 5 and 6 on quantum algorithms,and a selection from Chapter 7 on physical implementations,and Chapters 8 through 10 to understand quantum error-correction,with an especial focus on Chapter 10. A one-semester course on quantum information could be based upon a selection of material from Chapters 1 through 3,depending on the background of the class.Following that,Chapters 8 through 10 on quantum error-correction,followed by Chapters 11 and 12 on quantum entropy and quantum information theory,respectively. A full year class could cover all material in the book,with time for additional readings selected from the 'History and further reading'section of several chapters.Quantum com- putation and quantum information also lend themselves ideally to independent research projects for students. Aside from classes on quantum computation and quantum information,there is another way we hope the book will be used,which is as the text for an introductory class in quan- tum mechanics for physics students.Conventional introductions to quantum mechanics rely heavily on the mathematical machinery of partial differential equations.We believe this often obscures the fundamental ideas.Quantum computation and quantum informa-
x Preface have not given it a treatment for fear of being obsolete before publication of the book. The implementation of quantum information processing machines has also developed into a fascinating and rich area, and we limit ourselves to but a single chapter on this subject. Clearly, much more can be said about physical implementations, but this would begin to involve many more areas of physics, chemistry, and engineering, which we do not have room for here. How to use this book This book may be used in a wide variety of ways. It can be used as the basis for a variety of courses, from short lecture courses on a specific topic in quantum computation and quantum information, through to full-year classes covering the entire field. It can be used for independent study by people who would like to learn just a little about quantum computation and quantum information, or by people who would like to be brought up to the research frontier. It is also intended to act as a reference work for current researchers in the field. We hope that it will be found especially valuable as an introduction for researchers new to the field. Note to the independent reader The book is designed to be accessible to the independent reader. A large number of exercises are peppered throughout the text, which can be used as self-tests for understanding of the material in the main text. The Table of Contents and end of chapter summaries should enable you to quickly determine which chapters you wish to study in most depth. The dependency diagram, Figure 1, will help you determine in what order material in the book may be covered. Note to the teacher This book covers a diverse range of topics, and can therefore be used as the basis for a wide variety of courses. A one-semester course on quantum computation could be based upon a selection of material from Chapters 1 through 3, depending on the background of the class, followed by Chapter 4 on quantum circuits, Chapters 5 and 6 on quantum algorithms, and a selection from Chapter 7 on physical implementations, and Chapters 8 through 10 to understand quantum error-correction, with an especial focus on Chapter 10. A one-semester course on quantum information could be based upon a selection of material from Chapters 1 through 3, depending on the background of the class. Following that, Chapters 8 through 10 on quantum error-correction, followed by Chapters 11 and 12 on quantum entropy and quantum information theory, respectively. A full year class could cover all material in the book, with time for additional readings selected from the ‘History and further reading’ section of several chapters. Quantum computation and quantum information also lend themselves ideally to independent research projects for students. Aside from classes on quantum computation and quantum information, there is another way we hope the book will be used, which is as the text for an introductory class in quantum mechanics for physics students. Conventional introductions to quantum mechanics rely heavily on the mathematical machinery of partial differential equations. We believe this often obscures the fundamental ideas. Quantum computation and quantum informaxiv
Preface XXV tion offers an excellent conceptual laboratory for understanding the basic concepts and unique aspects of quantum mechanics,without the use of heavy mathematical machinery. Such a class would focus on the introduction to quantum mechanics in Chapter 2,basic material on quantum circuits in Chapter 4,a selection of material on quantum algorithms from Chapters 5 and 6,Chapter 7 on physical implementations of quantum computation, and then almost any selection of material from Part III of the book,depending upon taste. Note to the student We have written the book to be as self-contained as possible.The main exception is that occasionally we have omitted arguments that one really needs to work through oneself to believe;these are usually given as exercises.Let us suggest that you should at least attempt all the exercises as you work through the book.With few exceptions the exercises can be worked out in a few minutes.If you are having a lot of difficulty with many of the exercises it may be a sign that you need to go back and pick up one or more key concepts. Further reading As already noted,each chapter concludes with a 'History and further reading'section. There are also a few broad-ranging references that might be of interest to readers. Preskill'se]superb lecture notes approach quantum computation and quantum infor- mation from a somewhat different point of view than this book.Good overview articles on specific subjects include(in order of their appearance in this book):Aharonov's review of quantum computation[Aha,Kitaev's review of algorithms and error-correction(Kit7 Mosca's thesis on quantum algorithms[Mos9,Fuchs'thesis[Fuc9]on distinguishability and distance measures in quantum information,Gottesman's thesis on quantum error- correctionG,Preskill's review of quantum error-correctionPre,Nielsen's thesis on quantum information theorylNie98),and the reviews of quantum information theory by Bennett and Shor[Bs98]and by Bennett and DiVincenzolBD00.Other useful references include Gruska's book[Gru991,and the collection of review articles edited by Lo,Spiller, and PopesculLSP98]. Errors Any lengthy document contains errors and omissions,and this book is surely no exception to the rule.If you find any errors or have other comments to make about the book, please email them to:qci@squint.org.As errata are found,we will add them to a list maintained at the book web site:http://www.squint.org/qci/
Preface tion offers an excellent conceptual laboratory for understanding the basic concepts and unique aspects of quantum mechanics, without the use of heavy mathematical machinery. Such a class would focus on the introduction to quantum mechanics in Chapter 2, basic material on quantum circuits in Chapter 4, a selection of material on quantum algorithms from Chapters 5 and 6, Chapter 7 on physical implementations of quantum computation, and then almost any selection of material from Part III of the book, depending upon taste. Note to the student We have written the book to be as self-contained as possible. The main exception is that occasionally we have omitted arguments that one really needs to work through oneself to believe; these are usually given as exercises. Let us suggest that you should at least attempt all the exercises as you work through the book. With few exceptions the exercises can be worked out in a few minutes. If you are having a lot of difficulty with many of the exercises it may be a sign that you need to go back and pick up one or more key concepts. Further reading As already noted, each chapter concludes with a ‘History and further reading’ section. There are also a few broad-ranging references that might be of interest to readers. Preskill’s[Pre98b] superb lecture notes approach quantum computation and quantum information from a somewhat different point of view than this book. Good overview articles on specific subjects include (in order of their appearance in this book): Aharonov’s review of quantum computation[Aha99b], Kitaev’s review of algorithms and error-correction[Kit97b], Mosca’s thesis on quantum algorithms[Mos99], Fuchs’ thesis[Fuc96] on distinguishability and distance measures in quantum information, Gottesman’s thesis on quantum errorcorrection[Got97], Preskill’s review of quantum error-correction[Pre97], Nielsen’s thesis on quantum information theory[Nie98], and the reviews of quantum information theory by Bennett and Shor[BS98] and by Bennett and DiVincenzo[BD00]. Other useful references include Gruska’s book[Gru99], and the collection of review articles edited by Lo, Spiller, and Popescu[LSP98]. Errors Any lengthy document contains errors and omissions, and this book is surely no exception to the rule. If you find any errors or have other comments to make about the book, please email them to: qci@squint.org. As errata are found, we will add them to a list maintained at the book web site: http://www.squint.org/qci/. xxv
Acknowledgements A few people have decisively influenced how we think about quantum computation and quantum information.For many enjoyable discussions which have helped us shape and refine our views,MAN thanks Carl Caves,Chris Fuchs,Gerard Milburn,John Preskill and Ben Schumacher,and ILC thanks Tom Cover,Umesh Vazirani,Yoshi Yamamoto, and Bernie Yurke. An enormous number of people have helped in the construction of this book,both directly and indirectly.A partial list includes Dorit Aharonov,Andris Ambainis,Nabil Amer,Howard Barnum,Dave Beckman,Harry Buhrman,the Caltech Quantum Optics Foosballers,Andrew Childs,Fred Chong,Richard Cleve,John Conway,John Cortese, Michael DeShazo,Ronald de Wolf,David DiVincenzo,Steven van Enk,Henry Everitt, Ron Fagin,Mike Freedman,Michael Gagen,Neil Gershenfeld,Daniel Gottesman,Jim Harris,Alexander Holevo,Andrew Huibers,Julia Kempe,Alesha Kitaev,Manny Knill, Shing Kong,Raymond Laflamme,Andrew Landahl,Ron Legere,Debbie Leung,Daniel Lidar,Elliott Lieb,Theresa Lynn,Hideo Mabuchi,Yu Manin,Mike Mosca,Alex Pines, Sridhar Rajagopalan,Bill Risk,Beth Ruskai,Sara Schneider,Robert Schrader,Peter Shor,Sheri Stoll,Volker Strassen,Armin Uhlmann,Lieven Vandersypen,Anne Ver- hulst,Debby Wallach,Mike Westmoreland,Dave Wineland,Howard Wiseman,John Yard,Xinlan Zhou,and Wojtek Zurek. Thanks to the folks at Cambridge University Press for their help turning this book from an idea into reality.Our especial thanks go to our thoughtful and enthusiastic editor Simon Capelin,who shepherded this project along for more than three years,and to Margaret Patterson,for her timely and thorough copy-editing of the manuscript. Parts of this book were completed while MAN was a Tolman Prize Fellow at the California Institute of Technology,a member of the T-6 Theoretical Astrophysics Group at the Los Alamos National Laboratory,and a member of the University of New Mexico Center for Advanced Studies,and while ILC was a Research Staff Member at the IBM Almaden Research Center,a consulting Assistant Professor of Electrical Engineering at Stanford University,a visiting researcher at the University of California Berkeley Department of Computer Science,a member of the Los Alamos National Laboratory T-6 Theoretical Astrophysics Group,and a visiting researcher at the University of California Santa Barbara Institute for Theoretical Physics.We also appreciate the warmth and hospitality of the Aspen Center for Physics,where the final page proofs of this book were finished. MAN and ILC gratefully acknowledge support from DARPA under the NMRQC research initiative and the QUIC Institute administered by the Army Research Office. We also thank the National Science Foundation,the National Security Agency,the Office of Naval Research,and IBM for their generous support
Acknowledgements A few people have decisively influenced how we think about quantum computation and quantum information. For many enjoyable discussions which have helped us shape and refine our views, MAN thanks Carl Caves, Chris Fuchs, Gerard Milburn, John Preskill and Ben Schumacher, and ILC thanks Tom Cover, Umesh Vazirani, Yoshi Yamamoto, and Bernie Yurke. An enormous number of people have helped in the construction of this book, both directly and indirectly. A partial list includes Dorit Aharonov, Andris Ambainis, Nabil Amer, Howard Barnum, Dave Beckman, Harry Buhrman, the Caltech Quantum Optics Foosballers, Andrew Childs, Fred Chong, Richard Cleve, John Conway, John Cortese, Michael DeShazo, Ronald de Wolf, David DiVincenzo, Steven van Enk, Henry Everitt, Ron Fagin, Mike Freedman, Michael Gagen, Neil Gershenfeld, Daniel Gottesman, Jim Harris, Alexander Holevo, Andrew Huibers, Julia Kempe, Alesha Kitaev, Manny Knill, Shing Kong, Raymond Laflamme, Andrew Landahl, Ron Legere, Debbie Leung, Daniel Lidar, Elliott Lieb, Theresa Lynn, Hideo Mabuchi, Yu Manin, Mike Mosca, Alex Pines, Sridhar Rajagopalan, Bill Risk, Beth Ruskai, Sara Schneider, Robert Schrader, Peter Shor, Sheri Stoll, Volker Strassen, Armin Uhlmann, Lieven Vandersypen, Anne Verhulst, Debby Wallach, Mike Westmoreland, Dave Wineland, Howard Wiseman, John Yard, Xinlan Zhou, and Wojtek Zurek. Thanks to the folks at Cambridge University Press for their help turning this book from an idea into reality. Our especial thanks go to our thoughtful and enthusiastic editor Simon Capelin, who shepherded this project along for more than three years, and to Margaret Patterson, for her timely and thorough copy-editing of the manuscript. Parts of this book were completed while MAN was a Tolman Prize Fellow at the California Institute of Technology, a member of the T-6 Theoretical Astrophysics Group at the Los Alamos National Laboratory, and a member of the University of New Mexico Center for Advanced Studies, and while ILC was a Research Staff Member at the IBM Almaden Research Center, a consulting Assistant Professor of Electrical Engineering at Stanford University, a visiting researcher at the University of California Berkeley Department of Computer Science, a member of the Los Alamos National Laboratory T-6 Theoretical Astrophysics Group, and a visiting researcher at the University of California Santa Barbara Institute for Theoretical Physics. We also appreciate the warmth and hospitality of the Aspen Center for Physics, where the final page proofs of this book were finished. MAN and ILC gratefully acknowledge support from DARPA under the NMRQC research initiative and the QUIC Institute administered by the Army Research Office. We also thank the National Science Foundation, the National Security Agency, the Office of Naval Research, and IBM for their generous support
Nomenclature and notation There are several items of nomenclature and notation which have two or more meanings in common use in the field of quantum computation and quantum information.To prevent confusion from arising,this section collects many of the more frequently used of these items,together with the conventions that will be adhered to in this book. Linear algebra and quantum mechanics All vector spaces are assumed to be finite dimensional,unless otherwise noted.In many instances this restriction is unnecessary,or can be removed with some additional technical work,but making the restriction globally makes the presentation more easily comprehen- sible,and doesn't detract much from many of the intended applications of the results. A positive operator A is one for which (A)>0 for all )A positive definite operator A is one for which (A)>0 for all 0.The support of an operator is defined to be the vector space orthogonal to its kernel.For a Hermitian operator,this means the vector space spanned by eigenvectors of the operator with non-zero eigenvalues. The notation U(and often but not always V)will generically be used to denote a unitary operator or matrix.H is usually used to denote a quantum logic gate,the Hadamard gate,and sometimes to denote the Hamiltonian for a quantum system,with the meaning clear from context. Vectors will sometimes be written in column format,as for example, 1 2 (0.1) and sometimes for readability in the format(1,2).The latter should be understood as shorthand for a column vector.For two-level quantum systems used as qubits,we shall usually identify the state 0)with the vector (1,0),and similarly 1)with (0,1).We also define the Pauli sigma matrices in the conventional way-see 'Frequently used quantum gates and circuit symbols',below.Most significantly,the convention for the Pauli sigma z matrix is that o:0)=0)and o 1)=-1),which is reverse of what some physicists (but usually not computer scientists or mathematicians)intuitively expect.The origin of this dissonance is that the +1 eigenstate of o:is often identified by physicists with a so-called 'excited state',and it seems natural to many to identify this with 1),rather than with 0)as is done in this book.Our choice is made in order to be consistent with the usual indexing of matrix elements in linear algebra,which makes it natural to identify the first column of o:with the action of o:on 0),and the second column with the action on 1).This choice is also in use throughout the quantum computation and quantum information community.In addition to the conventional notations oz o and o=for the Pauli sigma matrices,it will also be convenient to use the notations o1,02,o3 for these
Nomenclature and notation There are several items of nomenclature and notation which have two or more meanings in common use in the field of quantum computation and quantum information. To prevent confusion from arising, this section collects many of the more frequently used of these items, together with the conventions that will be adhered to in this book. Linear algebra and quantum mechanics All vector spaces are assumed to be finite dimensional, unless otherwise noted. In many instances this restriction is unnecessary, or can be removed with some additional technical work, but making the restriction globally makes the presentation more easily comprehensible, and doesn’t detract much from many of the intended applications of the results. A positive operator A is one for which ψ|A|ψ ≥ 0 for all |ψ. A positive definite operator A is one for which ψ|A|ψ > 0 for all |ψ = 0. The support of an operator is defined to be the vector space orthogonal to its kernel. For a Hermitian operator, this means the vector space spanned by eigenvectors of the operator with non-zero eigenvalues. The notation U (and often but not always V ) will generically be used to denote a unitary operator or matrix. H is usually used to denote a quantum logic gate, the Hadamard gate, and sometimes to denote the Hamiltonian for a quantum system, with the meaning clear from context. Vectors will sometimes be written in column format, as for example, 1 2 , (0.1) and sometimes for readability in the format (1, 2). The latter should be understood as shorthand for a column vector. For two-level quantum systems used as qubits, we shall usually identify the state |0 with the vector (1, 0), and similarly |1 with (0, 1). We also define the Pauli sigma matrices in the conventional way – see ‘Frequently used quantum gates and circuit symbols’, below. Most significantly, the convention for the Pauli sigma z matrix is that σz|0 = |0 and σz|1 = −|1, which is reverse of what some physicists (but usually not computer scientists or mathematicians) intuitively expect. The origin of this dissonance is that the +1 eigenstate of σz is often identified by physicists with a so-called ‘excited state’, and it seems natural to many to identify this with |1, rather than with |0 as is done in this book. Our choice is made in order to be consistent with the usual indexing of matrix elements in linear algebra, which makes it natural to identify the first column of σz with the action of σz on |0, and the second column with the action on |1. This choice is also in use throughout the quantum computation and quantum information community. In addition to the conventional notations σx, σy and σz for the Pauli sigma matrices, it will also be convenient to use the notations σ1, σ2, σ3 for these
XXX Nomenclature and notation three matrices,and to define oo as the 2x2 identity matrix.Most often,however,we use the notations I,X,Y and Z for oo,01,02 and o3,respectively. Information theory and probability As befits good information theorists,logarithms are alvays taken to base two,unless otherwise noted.We use log(z)to denote logarithms to base 2,and In(r)on those rare occasions when we wish to take a natural logarithm.The term probability distribution is used to refer to a finite set of real numbers,pr,such that p>0 and p=1.The relative entropy of a positive operator A with respect to a positive operator B is defined byS(A‖B)≡tr(Alog A)-tr(Alog B) Miscellanea denotes modulo two addition.Throughout this book'z'is pronounced zed'. Frequently used quantum gates and circuit symbols Certain schematic symbols are often used to denote unitary transforms which are useful in the design of quantum circuits.For the reader's convenience,many of these are gathered together below.The rows and columns of the unitary transforms are labeled from left to right and top to bottom as 00...0,00...I to 11...1 with the bottom-most wire being the least significant bit.Note that e/4 is the square root of i,so that the /8 gate is the square root of the phase gate,which itself is the square root of the Pauli-Z gate. Hadamard 1 1 -1 Pauli-X 10 Pauli-Y Pauli-Z [8 Phase ] 元/8 远 0
Nomenclature and notation three matrices, and to define σ0 as the 2×2 identity matrix. Most often, however, we use the notations I, X, Y and Z for σ0, σ1, σ2 and σ3, respectively. Information theory and probability As befits good information theorists, logarithms are always taken to base two, unless otherwise noted. We use log(x) to denote logarithms to base 2, and ln(x) on those rare occasions when we wish to take a natural logarithm. The term probability distribution is used to refer to a finite set of real numbers, px, such that px ≥ 0 and x px = 1. The relative entropy of a positive operator A with respect to a positive operator B is defined by S(A||B) ≡ tr(A log A) − tr(A log B). Miscellanea ⊕ denotes modulo two addition. Throughout this book ‘z’ is pronounced ‘zed’. Frequently used quantum gates and circuit symbols Certain schematic symbols are often used to denote unitary transforms which are useful in the design of quantum circuits. For the reader’s convenience, many of these are gathered together below. The rows and columns of the unitary transforms are labeled from left to right and top to bottom as 00 ... 0, 00 ... 1 to 11 ... 1 with the bottom-most wire being the least significant bit. Note that eiπ/4 is the square root of i, so that the π/8 gate is the square root of the phase gate, which itself is the square root of the Pauli-Z gate. Hadamard 1 √ 2 1 1 1 −1 Pauli-X 0 1 1 0 Pauli-Y 0 −i i 0 Pauli-Z 1 0 0 −1 Phase 1 0 0 i π/8 1 0 0 eiπ/4 xxx