QuantumComputationandQuantumInformation
Michael A. Nielsen& Isaac L. Chuang
PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE
ThePitt Building,TrumpingtonStreet,Cambridge, UnitedKingdom
CAMBRIDGE UNIVERSITY PRESS
TheEdinburghBuilding,Cambridge CB22RU,UK www.cup.cam.ac.uk
40West 20th Street,NewYork, NY 10011-4211, USA www.cup.org
10StamfordRoad,Oakleigh, Melbourne3166, Australia
RuizdeAlarcon ? 13,28014 Madrid,Spain
c Cambridge UniversityPress 2000
Thisbook isin copyright.Subjectto statutory exception
andtotheprovisions ofrelevantcollectivelicensingagreements,
noreproductionofanypartmaytakeplacewithout
thewrittenpermission of Cambridge UniversityPress.
First published2000
PrintedintheUnitedKingdom attheUniversityPress, Cambridge
1
A
TypefaceMonotypeEhrhardt10 /13pt SystemLTX2" [EPC]
E
2
Acataloguerecordofthisbook isavailablefromtheBritishLibrary
LibraryofCongressCataloguinginPublicationdata
Nielsen,MichaelA., andChuang,IsaacL.
QuantumComputationandQuantumInformation/MichaelA.NielsenandIsaacL.Chuang.
p. cm.
Includesbibliographical referencesandindex.
ISBN0-521-63503-9
1. Physics. I. Title.
QA401.G47 2000
0
511 .8{dc21 98-22029 CIP
ISBN052163235 8hardback
ISBN052163503 9paperbackContents
Preface pagexv
Acknowledgements xxi
Nomenclatureandnotation xxiii
PartI Fundamentalconcepts 1
1 Introductionandoverview 1
1.1 Globalperspectives 1
1.1.1 Historyof quantum computation and quantum information 2
1.1.2 Future directions 12
1.2 Quantum bits 13
1.2.1 Multiplequbits 16
1.3 Quantum computation 17
1.3.1 Singlequbit gates 17
1.3.2 Multiplequbit gates 20
1.3.3 Measurements inbases other than the computational basis 22
1.3.4 Quantum circuits 22
1.3.5 Qubitcopyingcircuit? 24
1.3.6 Example:Bellstates 25
1.3.7 Example: quantum teleportation 26
1.4 Quantum algorithms 28
1.4.1 Classical computations ona quantum computer 29
1.4.2 Quantum parallelism 30
1.4.3 Deutsch’s algorithm 32
1.4.4 TheDeutsch{Jozsa algorithm 34
1.4.5 Quantum algorithms summarized 36
1.5 Experimental quantum information processing 42
1.5.1 TheStern{Gerlach experiment 43
1.5.2 Prospects forpractical quantum informationprocessing 46
1.6 Quantum information 50
1.6.1 Quantum information theory: example problems 52
1.6.2 Quantum information inawider context 58
2 Introductiontoquantummechanics 60
2.1 Linear algebra 61
2.1.1 Bases and linear independence 62
2.1.2 Linear operators andmatrices 63viii Contents
2.1.3 ThePaulimatrices 65
2.1.4 Inner products 65
2.1.5 Eigenvectors andeigenvalues 68
2.1.6 Adjoints and Hermitian operators 69
2.1.7 Tensorproducts 71
2.1.8 Operator functions 75
2.1.9 The commutator and anti-commutator 76
2.1.10 Thepolarand singularvaluedecompositions 78
2.2 The postulates of quantum mechanics 80
2.2.1 State space 80
2.2.2 Evolution 81
2.2.3 Quantum measurement 84
2.2.4 Distinguishing quantum states 86
2.2.5 Projective measurements 87
2.2.6 POVMmeasurements 90
2.2.7 Phase 93
2.2.8 Composite systems 93
2.2.9 Quantum mechanics: aglobal view 96
2.3 Application: superdense coding 97
2.4 The density operator 98
2.4.1 Ensemblesof quantum states 99
2.4.2 General properties ofthe density operator 101
2.4.3 The reduced density operator 105
2.5 The Schmidt decomposition and puri?cations 109
2.6 EPRand theBellinequality 111
3 Introductiontocomputerscience 120
3.1 Modelsforcomputation 122
3.1.1 Turingmachines 122
3.1.2 Circuits 129
3.2 Theanalysisofcomputational problems 135
3.2.1 How toquantify computational resources 136
3.2.2 Computational complexity 138
3.2.3 Decisionproblemsandthe complexity classesP andNP 141
3.2.4 A plethora ofcomplexity classes 150
3.2.5 Energy and computation 153
3.3 Perspectives on computer science 161
PartII Quantumcomputation 171
4 Quantumcircuits 171
4.1 Quantum algorithms 172
4.2 Singlequbitoperations 174
4.3 Controlledoperations 177
4.4 Measurement 185
4.5 Universalquantum gates 188
Contents ix
4.5.1 Two-levelunitary gates are universal 189
4.5.2 Singlequbitand gates areuniversal 191
4.5.3 Adiscreteset ofuniversal operations 194
4.5.4 Approximating arbitraryunitary gates isgenerically hard 198
4.5.5 Quantum computational complexity 200
4.6 Summary ofthe quantum circuitmodel ofcomputation 202
4.7 Simulationof quantum systems 204
4.7.1 Simulationinaction 204
4.7.2 Thequantum simulationalgorithm 206
4.7.3 Anillustrativeexample 209
4.7.4 Perspectives onquantum simulation 211
5 ThequantumFouriertransformanditsapplications 216
5.1 Thequantum Fouriertransform 217
5.2 Phase estimation 221
5.2.1 Performance and requirements 223
5.3 Applications: order-?nding and factoring 226
5.3.1 Application: order-?nding 226
5.3.2 Application: factoring 232
5.4 General applications of the quantum Fourier transform 234
5.4.1 Period-?nding 236
5.4.2 Discrete logarithms 238
5.4.3 Thehidden subgroupproblem 240
5.4.4 Otherquantum algorithms? 242
6 Quantumsearchalgorithms 248
6.1 Thequantum search algorithm 248
6.1.1 Theoracle 248
6.1.2 Theprocedure 250
6.1.3 Geometric visualization 252
6.1.4 Performance 253
6.2 Quantum search as a quantum simulation 255
6.3 Quantum counting 261
6.4 Speeding upthe solutionofNP-complete problems 263
6.5 Quantum search ofan unstructured database 265
6.6 Optimalityofthe search algorithm 269
6.7 Black boxalgorithmlimits 271
7 Quantumcomputers:physicalrealization 277
7.1 Guiding principles 277
7.2 Conditionsforquantum computation 279
7.2.1 Representation ofquantum information 279
7.2.2 Performance ofunitary transformations 281
7.2.3 Preparation of ?ducial initialstates 281
7.2.4 Measurement ofoutput result 282
7.3 Harmonicoscillatorquantum computer 283
7.3.1 Physicalapparatus 283x Contents
7.3.2 TheHamiltonian 284
7.3.3 Quantum computation 286
7.3.4 Drawbacks 286
7.4 Optical photon quantum computer 287
7.4.1 Physical apparatus 287
7.4.2 Quantum computation 290
7.4.3 Drawbacks 296
7.5 Optical cavity quantum electrodynamics 297
7.5.1 Physical apparatus 298
7.5.2 TheHamiltonian 300
7.5.3 Single-photon single-atomabsorptionand refraction 303
7.5.4 Quantum computation 306
7.6 Ion traps 309
7.6.1 Physical apparatus 309
7.6.2 TheHamiltonian 317
7.6.3 Quantum computation 319
7.6.4 Experiment 321
7.7 Nuclear magnetic resonance 324
7.7.1 Physical apparatus 325
7.7.2 TheHamiltonian 326
7.7.3 Quantum computation 331
7.7.4 Experiment 336
7.8 Other implementation schemes 343
PartIII Quantuminformation 353
8 Quantumnoiseandquantumoperations 353
8.1 Classicalnoiseand Markovprocesses 354
8.2 Quantum operations 356
8.2.1 Overview 356
8.2.2 Environments and quantum operations 357
8.2.3 Operator-sum representation 360
8.2.4 Axiomatic approach toquantum operations 366
8.3 Examples ofquantum noiseand quantum operations 373
8.3.1 Trace and partial trace 374
8.3.2 Geometric picture ofsinglequbit quantum operations 374
8.3.3 Bit ip and phase ipchannels 376
8.3.4 Depolarizing channel 378
8.3.5 Amplitude damping 380
8.3.6 Phase damping 383
8.4 Applications of quantum operations 386
8.4.1 Master equations 386
8.4.2 Quantum process tomography 389
8.5 Limitations ofthequantum operations formalism 394
Contents xi
9 Distancemeasuresforquantuminformation 399
9.1 Distance measures for classicalinformation 399
9.2 Howcloseare twoquantum states? 403
9.2.1 Tracedistance 403
9.2.2 Fidelity 409
9.2.3 Relationships between distance measures 415
9.3 How well does a quantum channel preserve information? 416
10 Quantumerror-correction 425
10.1 Introduction 426
10.1.1 Thethree qubitbitipcode 427
10.1.2 Threequbitphase ipcode 430
10.2 TheShorcode 432
10.3 Theoryofquantum error-correction 435
10.3.1 Discretizationofthe errors 438
10.3.2 Independent error models 441
10.3.3 Degenerate codes 444
10.3.4 Thequantum Hamming bound 444
10.4 Constructing quantum codes 445
10.4.1 Classicallinearcodes 445
10.4.2 Calderbank{Shor{Steane codes 450
10.5 Stabilizercodes 453
10.5.1 Thestabilizerformalism 454
10.5.2 Unitary gatesand the stabilizerformalism 459
10.5.3 Measurement inthe stabilizerformalism 463
10.5.4 TheGottesman{Knill theorem 464
10.5.5 Stabilizercode constructions 464
10.5.6 Examples 467
10.5.7 Standard formfor astabilizercode 470
10.5.8 Quantum circuits for encoding, decoding, and correction 472
10.6 Fault-tolerant quantum computation 474
10.6.1 Fault-tolerance: the bigpicture 475
10.6.2 Fault-tolerant quantum logic 482
10.6.3 Fault-tolerant measurement 489
10.6.4 Elements ofresilientquantum computation 493
11 Entropyandinformation 500
11.1 Shannon entropy 500
11.2 Basic properties ofentropy 502
11.2.1 Thebinaryentropy 502
11.2.2 Therelativeentropy 504
11.2.3 Conditional entropy and mutual information 505
11.2.4 Thedata processing inequality 509
11.3 VonNeumann entropy 510
11.3.1 Quantum relativeentropy 511
11.3.2 Basic properties ofentropy 513
11.3.3 Measurements and entropy 514xii Contents
11.3.4 Subadditivity 515
11.3.5 Concavity of the entropy 516
11.3.6 The entropy ofa mixture ofquantum states 518
11.4 Strong subadditivity 519
11.4.1 Proofof strongsubadditivity 519
11.4.2 Strong subadditivity:elementary applications 522
12 Quantuminformationtheory 528
12.1 Distinguishing quantum states and the accessibleinformation 529
12.1.1 TheHolevobound 531
12.1.2 Example applications of the Holevobound 534
12.2 Data compression 536
12.2.1 Shannon’s noiselesschannel coding theorem 537
12.2.2 Schumacher’s quantum noiseless channel coding theorem 542
12.3 Classicalinformationovernoisyquantum channels 546
12.3.1 Communication overnoisyclassicalchannels 548
12.3.2 Communication overnoisyquantum channels 554
12.4 Quantum information over noisy quantum channels 561
12.4.1 Entropy exchange and the quantum Fano inequality 561
12.4.2 The quantum dataprocessing inequality 564
12.4.3 Quantum Singleton bound 568
12.4.4 Quantum error-correction,refrigerationandMaxwell’sdemon 569
12.5 Entanglement asaphysical resource 571
12.5.1 Transforming bi-partitepure state entanglement 573
12.5.2 Entanglement distillationanddilution 578
12.5.3 Entanglement distillationandquantum error-correction 580
12.6 Quantum cryptography 582
12.6.1 Private keycryptography 582
12.6.2 Privacy ampli?cationand informationreconciliation 584
12.6.3 Quantum keydistribution 586
12.6.4 Privacy andcoherent information 592
12.6.5 The security ofquantum keydistribution 593
Appendices 608
Appendix1: Notesonbasicprobability theory 608
Appendix2: Grouptheory 610
A2.1 Basic de?nitions 610
A2.1.1 Generators 611
A2.1.2 Cyclicgroups 611
A2.1.3 Cosets 612
A2.2 Representations 612
A2.2.1 Equivalence and reducibility 612
A2.2.2 Orthogonality 613
A2.2.3 The regular representation 614Contents xiii
A2.3 Fouriertransforms 615
Appendix3: TheSolovay{Kitaev theorem 617
Appendix4: Numbertheory 625
A4.1 Fundamentals 625
A4.2 Modulararithmetic andEuclid’salgorithm 626
A4.3 Reduction offactoring to order-?nding 633
A4.4 Continued fractions 635
Appendix5: Publickeycryptography andtheRSAcryptosystem 640
Appendix6: ProofofLieb’stheorem 645
Bibliography 649
Index 665I Fundamentalconcepts
1 Introduction andoverview
Science offers the boldest metaphysics of the age. It is a thoroughly human
construct,drivenbythefaiththatifwedream,presstodiscover,explain,and
dreamagain,therebyplungingrepeatedlyintonewterrain,theworldwillsome-
how come clearer and we will grasp the true strangeness of the universe. And
thestrangenesswillallprovetobeconnected,andmakesense.
{EdwardO.Wilson
Informationisphysical.
{ Rolf Landauer
Whatarethefundamental concepts ofquantum computationandquantum information?
Howdidtheseconcepts develop? Towhat usesmay they beput? Howwillthey bepre-
sentedinthisbook?Thepurposeofthisintroductorychapteristoanswerthesequestions
by developing in broad brushstrokes a picture of the ?eld of quantum computation and
quantum information.Theintentistocommunicateabasicunderstanding ofthecentral
concepts of the ?eld, perspective on how they have been developed, and to help you
decide howto approach the rest ofthe book.
Our story begins in Section 1.1 with an account of the historical context in which
quantum computation and quantum information has developed. Each remaining section
in the chapter gives a brief introduction to one or more fundamental concepts from the
?eld: quantum bits(Section 1.2),quantum computers, quantum gates and quantum cir-
cuits(Section1.3),quantumalgorithms(Section1.4),experimentalquantuminformation
processing (Section 1.5), and quantum information and communication (Section 1.6).
Along the way, illustrative and easily accessible developments such as quantum tele-
portation and some simple quantum algorithms are given, using the basic mathematics
taught in this chapter. The presentation is self-contained, and designed to be accessible
even without a background in computer science or physics. As we move along, we give
pointerstomorein-depthdiscussionsinlaterchapters,wherereferencesandsuggestions
for further reading may alsobe found.
If as you read you’re ?nding the going rough, skip on to a spot where you feel more
comfortable. Atpoints wehaven’t been ableto avoid using alittle technical lingowhich
won’tbecompletelyexplaineduntillaterinthebook.Simplyacceptitfornow,andcome
backlaterwhenyouunderstand alltheterminologyinmoredetail.Theemphasisinthis
?rstchapter isonthebigpicture, withthedetails tobe?lledinlater.
1.1 Globalperspectives
Quantumcomputationandquantuminformationisthestudyoftheinformationprocess-
ing tasks that can be accomplished using quantum mechanical systems. Sounds pretty2 Introductionandoverview
simpleand obvious,doesn’t it?Likemany simplebutprofound ideas it wasalongtime
beforeanybodythoughtofdoinginformationprocessingusingquantum mechanicalsys-
tems. To see why this is the case, we must go back in time and look in turn at each
of the ?elds which have contributed fundamental ideas to quantum computation and
quantum information { quantum mechanics, computer science, information theory, and
cryptography. As we take our short historical tour of these ?elds, think of yourself ?rst
as a physicist, then as a computer scientist, then as an information theorist, and ?nally
as a cryptographer, in order to get some feel for the disparate perspectives which have
come together inquantum computation and quantum information.
1.1.1 Historyofquantumcomputationandquantuminformation
Ourstorybeginsatthe turnofthetwentieth century when aunheralded revolutionwas
underway in science. A series of crises had arisen in physics. The problem was that the
theoriesofphysicsatthattime(nowdubbedclassicalphysics)werepredictingabsurdities
suchastheexistenceofan‘ultravioletcatastrophe’involvingin?niteenergies,orelectrons
spiraling inexorably into the atomic nucleus. At ?rst such problems were resolved with
the addition of ad hoc hypotheses to classical physics, but as a better understanding
of atoms and radiation was gained these attempted explanations became more and more
convoluted.Thecrisiscametoaheadintheearly1920safteraquartercenturyofturmoil,
and resulted in the creation of the modern theory of quantum mechanics. Quantum
mechanics has been an indispensable part of science ever since, and has been applied
with enormous success to everything under and inside the Sun, including the structure
of the atom, nuclear fusion in stars, superconductors, the structure of DNA, and the
elementary particles of Nature.
Whatisquantummechanics?Quantummechanicsisamathematicalframeworkorset
ofrulesfortheconstructionofphysicaltheories.Forexample,thereisaphysicaltheory
knownasquantumelectrodynamics whichdescribeswithfantasticaccuracy theinterac-
tion of atoms and light. Quantum electrodynamics is built up within the framework of
quantummechanics,butitcontainsspeci?crulesnotdeterminedbyquantummechanics.
The relationship of quantum mechanics to speci?c physical theories like quantum elec-
trodynamics is rather like the relationship of a computer’s operating system to speci?c
applications software { the operating system sets certain basicparameters and modes of
operation, butleaves open how speci?c tasks are accomplished by the applications.
The rules of quantum mechanics are simple but even experts ?nd them counter-
intuitive,andtheearliestantecedentsofquantumcomputationandquantuminformation
may be found in the long-standing desire of physicists to better understand quantum
mechanics. The best known critic of quantum mechanics, Albert Einstein, went to his
graveunreconciledwiththetheoryhehelpedinvent.Generationsofphysicistssincehave
wrestled with quantum mechanics in an effort to make its predictions more palatable.
One of the goals of quantum computation and quantum information is to develop tools
which sharpen our intuition about quantum mechanics, and make its predictions more
transparent to human minds.
For example, inthe early 1980s,interest aroseinwhether it might bepossibleto use
quantumeffectstosignalfasterthanlight{abigno-noaccordingtoEinstein’stheoryof
relativity.Theresolutionof thisproblemturns out to hingeonwhether itispossibleto
clone anunknownquantum state,thatis,constructacopyofaquantum state.Ifcloning
werepossible,thenitwouldbepossibletosignalfasterthanlightusingquantumeffects.Globalperspectives 3
However,cloning{soeasytoaccomplishwithclassicalinformation(considerthewords
in frontof you, and where they came from!){ turns out not to bepossibleingeneral in
quantum mechanics. This no-cloning theorem, discovered in the early 1980s, is one of
theearliestresultsofquantumcomputationandquantuminformation.Manyre?nements
oftheno-cloningtheoremhavesincebeendeveloped,andwenowhaveconceptual tools
whichallowustounderstandhowwella(necessarilyimperfect)quantum cloningdevice
might work. These tools, in turn, have been applied to understand other aspects of
quantum mechanics.
A related historical strand contributing to the development of quantum computation
andquantuminformationistheinterest,datingtothe1970s,ofobtainingcompletecon-
troloversinglequantumsystems.Applicationsofquantummechanicspriortothe1970s
typically involved a gross level of control over a bulk sample containing an enormous
number ofquantum mechanical systems,noneofthem directly accessible.Forexample,
superconductivityhasasuperbquantummechanicalexplanation.However,becauseasu-
perconductorinvolvesahuge(comparedtotheatomicscale)sampleofconductingmetal,
we can only probe a few aspects of its quantum mechanical nature, with the individual
quantum systems constituting the superconductor remaining inaccessible. Systems such
as particle accelerators do allowlimitedaccess to individual quantum systems,butagain
provide littlecontroloverthe constituent systems.
Since the 1970s many techniques for controlling single quantum systems have been
developed. For example, methods have been developed for trapping a single atom in an
‘atomtrap’,isolatingitfromtherestoftheworldandallowingustoprobemanydifferent
aspects of its behavior with incredible precision. The scanning tunneling microscope
has been used to move single atoms around, creating designer arrays of atoms at will.
Electronic devices whose operation involves the transfer of only single electrons have
been demonstrated.
Why all this effort to attain complete control over single quantum systems? Setting
aside the many technological reasons and concentrating on pure science, the principal
answer is that researchers have done this on a hunch. Often the most profound insights
in science come when we develop a method for probing a new regime of Nature. For
example, the invention of radio astronomy in the 1930s and 1940s led to a spectacular
sequenceofdiscoveries,includingthegalacticcoreoftheMilkyWaygalaxy,pulsars,and
quasars. Lowtemperature physicshas achieveditsamazing successes by?nding waysto
lower the temperatures of different systems. In a similar way, by obtaining complete
control over single quantum systems, we are exploring untouched regimes of Nature in
thehopeofdiscoveringnewandunexpectedphenomena.Wearejustnowtakingour?rst
steps along these lines, and already a few interesting surprises have been discovered in
this regime.What else shallwediscoveras weobtainmore complete controloversingle
quantum systems, and extend ittomore complex systems?
Quantumcomputationandquantuminformation?tnaturallyintothisprogram.They
provide a useful series of challenges at varied levels of dif?culty for people devising
methodstobettermanipulatesinglequantumsystems,andstimulatethedevelopmentof
new experimental techniques and provide guidance as to the mostinteresting directions
in which to take experiment. Conversely, the ability to control single quantum systems
is essential if we are to harness the power of quantum mechanics for applications to
quantum computation and quantum information.
Despitethisintenseinterest,effortstobuildquantuminformationprocessingsystems4 Introductionandoverview
have resulted in modest success to date. Small quantum computers, capable of doing
dozensofoperationsonafewqubitsrepresentthestateoftheartinquantumcomputation.
Experimentalprototypesfordoingquantumcryptography {awayofcommunicating in
secretacrosslongdistances{havebeendemonstrated,andareevenatthelevelwherethey
may be useful for some real-world applications. However, it remains a great challenge
to physicists and engineers of the future to develop techniques for making large-scale
quantum information processing areality.
Letusturnourattentionfromquantummechanics toanotherofthegreatintellectual
triumphs of the twentieth century, computer science. The origins of computer science
arelostinthedepthsofhistory.Forexample,cuneiformtabletsindicatethatbythetime
ofHammurabi(circa1750B.C.)theBabylonianshaddevelopedsomefairlysophisticated
algorithmicideas, anditislikelythatmany ofthoseideasdate toevenearlier times.
Themodernincarnationofcomputer sciencewasannounced bythegreatmathemati-
cian Alan Turing in a remarkable 1936 paper. Turing developed in detail an abstract
notion of what we would now call a programmable computer, a model for computation
nowknownastheTuringmachine,inhishonor.TuringshowedthatthereisaUniversal
TuringMachine that can beused tosimulate any other Turingmachine. Furthermore,
heclaimedthattheUniversalTuringMachinecompletelycaptureswhatitmeanstoper-
formataskbyalgorithmicmeans.Thatis,ifanalgorithmcanbeperformedonanypiece
of hardware (say, a modern personal computer), then there is an equivalent algorithm
for a Universal Turing Machine which performs exactly the same task as the algorithm
running on the personal computer. This assertion, known as theChurch{Turing thesis
inhonorofTuringandanotherpioneerofcomputerscience,AlonzoChurch,assertsthe
equivalence between the physical concept of what class of algorithms can be performed
onsomephysical device with the rigorous mathematical concept of a Universal Turing
Machine.Thebroadacceptance ofthisthesislaidthefoundationforthedevelopmentof
arich theory ofcomputer science.
Not long after Turing’s paper, the ?rst computers constructed from electronic com-
ponents were developed. John von Neumann developed a simple theoretical model for
how to put together in a practical fashion all the components necessary for a computer
tobefullyascapableasaUniversalTuringMachine. Hardwaredevelopment trulytook
off,though,in1947,whenJohnBardeen, WalterBrattain, andWillShockleydeveloped
thetransistor.Computerhardwarehasgrowninpoweratanamazingpaceeversince,so
muchsothatthegrowthwascodi?edbyGordonMoorein1965inwhathascometobe
known asMoore’slaw, which states that computer power will double for constant cost
roughly once every two years.
Amazingly enough, Moore’s law has approximately held true in the decades since
the 1960s. Nevertheless, most observers expect that this dream run will end some time
during the ?rst two decades of the twenty-?rst century. Conventional approaches to
the fabrication of computer technology are beginning to run up against fundamental
dif?culties of size. Quantum effects are beginning to interfere in the functioning of
electronic devices as they aremade smaller and smaller.
One possible solution to the problem posed by the eventual failure of Moore’s law
is to move to a different computing paradigm. One such paradigm is provided by the
theoryofquantumcomputation,whichisbasedontheideaofusingquantummechanics
toperformcomputations, insteadofclassicalphysics.Itturnsoutthatwhileanordinary
computer can be used to simulate a quantum computer, it appears to be impossible toGlobalperspectives 5
performthesimulationinanef?cientfashion.Thusquantumcomputersofferanessential
speedadvantageoverclassicalcomputers.Thisspeedadvantageissosigni?cantthatmany
researchersbelievethatnoconceivableamountofprogressinclassicalcomputationwould
beabletoovercomethegapbetweenthepowerofaclassicalcomputerandthepowerof
a quantum computer.
Whatdowemeanby‘ef?cient’versus‘inef?cient’simulationsofaquantumcomputer?
Many of the key notions needed to answer this question were actually invented before
the notion of a quantum computer had even arisen. In particular, the idea of ef?cient
andinef?cientalgorithmswasmademathematicallyprecisebythe?eldofcomputational
complexity.Roughlyspeaking,anef?cientalgorithmisonewhichrunsintimepolynomial
in the size of the problem solved. In contrast, an inef?cient algorithm requires super-
polynomial (typically exponential) time. What was noticed in the late 1960s and early
1970s was that it seemed as though the Turing machine model of computation was at
least as powerful as any other model of computation, in the sense that a problem which
couldbesolvedef?ciently insomemodelofcomputation couldalsobesolvedef?ciently
intheTuringmachinemodel,byusingtheTuringmachinetosimulatetheothermodel
ofcomputation.Thisobservationwascodi?edintoastrengthenedversionoftheChurch{
Turingthesis:
Anyalgorithmic processcanbesimulated ef?ciently usingaTuring machine.
The key strengthening in the strong Church{Turing thesis is the word ef?ciently.If
the strong Church{Turing thesis is correct, then it implies that no matter what type of
machine we use to perform our algorithms, that machine can be simulated ef?ciently
using a standard Turing machine. This is an important strengthening, as it implies that
for the purposes of analyzing whether a given computational task can be accomplished
ef?ciently, we may restrict ourselves to the analysis of the Turing machine model of
computation.
One class of challenges to the strong Church{Turing thesis comes from the ?eld of
analogcomputation.IntheyearssinceTuring,manydifferentteamsofresearchershave
noticed that certain types ofanalog computers can ef?ciently solveproblemsbelievedto
have no ef?cient solution on a Turing machine. At ?rst glance these analog computers
appear toviolatethestrongformoftheChurch{Turingthesis.Unfortunately foranalog
computation, itturns outthat whenrealisticassumptions about thepresence ofnoisein
analog computers are made, their power disappears in all known instances; they cannot
ef?ciently solve problems which are not ef?ciently solvable on a Turing machine. This
lesson { that the effects of realistic noise must be taken into account in evaluating the
ef?ciency of a computational model { was one of the great early challenges of quantum
computationandquantum information,achallengesuccessfullymetbythedevelopment
ofatheoryofquantumerror-correctingcodesandfault-tolerantquantumcomputation.
Thus,unlikeanalogcomputation,quantum computationcaninprincipletoleratea?nite
amount ofnoise and stillretain its computational advantages.
The?rstmajorchallengetothestrongChurch{Turingthesisaroseinthemid1970s,
whenRobertSolovayandVolkerStrassenshowedthatitispossibletotestwhetheranin-
tegerisprimeorcompositeusingarandomizedalgorithm.Thatis,theSolovay{Strassen
test for primality used randomness as anessential part of the algorithm. The algorithm
didnotdeterminewhetheragivenintegerwasprimeorcompositewithcertainty.Instead,
thealgorithmcoulddeterminethatanumberwasprobablyprimeorelsecompositewith6 Introductionandoverview
certainty. By repeating the Solovay{Strassentestafewtimesitispossibletodetermine
with near certainty whether a number is prime or composite. Of especial interest at the
time the Solovay{Strassen test was proposed was that no ef?cient deterministic test for
primality was known. Thus, it seemed as though computers with access to a random
number generator would beableto ef?ciently performcomputational tasks with no ef?-
cient solution on a conventional deterministic Turing machine. This discovery inspired
a search for other randomized algorithms which has paid off handsomely, with the ?eld
blossomingintoathrivingareaofresearch.
RandomizedalgorithmsposeachallengetothestrongChurch{Turingthesis,suggest-
ing that there are ef?ciently soluble problems which, nevertheless, cannot be ef?ciently
solved on a deterministic Turing machine. This challenge appears to be easily resolved
bya simplemodi?cation ofthe strong Church{Turing thesis:
Anyalgorithmic processcanbesimulated ef?ciently usinga
probabilistic Turingmachine.
This ad hoc modi?cation of the strong Church{Turing thesis should leave you feeling
ratherqueasy.Mightitnotturnoutatsomelaterdatethatyetanothermodelofcomputa-
tionallowsonetoef?cientlysolveproblemsthatarenotef?cientlysolublewithinTuring’s
modelofcomputation?Isthereanywaywecan?ndasinglemodelofcomputationwhich
isguaranteed to beabletoef?ciently simulateany other modelofcomputation?
Motivatedbythisquestion,in1985DavidDeutschaskedwhetherthelawsofphysics
couldbeusetoderive anevenstrongerversionoftheChurch{Turingthesis.Insteadof
adoptingadhoc hypotheses, Deutsch looked tophysical theory to provide a foundation
fortheChurch{Turingthesisthatwouldbeassecureasthestatusofthatphysicaltheory.
Inparticular,Deutschattempted tode?neacomputational devicethatwouldbecapable
of ef?ciently simulating an arbitrary physical system. Because the laws of physics are
ultimatelyquantummechanical,Deutschwasnaturallyledtoconsidercomputingdevices
based upon the principles of quantum mechanics. These devices, quantum analogues of
the machines de?ned forty-nine years earlier by Turing, led ultimately to the modern
conception ofa quantum computer usedinthisbook.
At the time of writing it is not clear whether Deutsch’s notion of a Universal Quan-
tum Computer is suf?cient to ef?ciently simulate an arbitrary physical system. Proving
or refuting this conjecture is one of the great open problems of the ?eld of quantum
computation and quantum information. It is possible, for example, that some effect of
quantum ?eld theory or an even more esoteric effect based in string theory, quantum
gravity or some other physical theory may take us beyond Deutsch’s Universal Quan-
tumComputer,givingusastillmorepowerfulmodelforcomputation. Atthisstage,we
simplydon’t know.
WhatDeutsch’smodelofaquantumcomputerdidenablewasachallengetothestrong
form of the Church{Turing thesis. Deutsch asked whether it is possible for a quantum
computertoef?cientlysolvecomputationalproblemswhichhavenoef?cientsolutionon
aclassicalcomputer,evenaprobabilisticTuringmachine.Hethenconstructed asimple
example suggesting that, indeed, quantum computers mighthave computational powers
exceeding those ofclassical computers.
This remarkable ?rst step taken by Deutsch was improved in the subsequent decade
by many people, culminating in Peter Shor’s 1994 demonstration that two enormously
importantproblems{theproblemof?ndingtheprimefactorsofaninteger,andtheso-Globalperspectives 7
called‘discretelogarithm’problem{couldbesolvedef?cientlyonaquantumcomputer.
This attracted widespread interest because these two problems were and still are widely
believedtohavenoef?cientsolutiononaclassicalcomputer.Shor’sresultsareapower-
ful indication that quantum computers are more powerful than Turing machines, even
probabilistic Turing machines. Further evidence for the power of quantum computers
camein1995whenLovGrovershowedthatanotherimportantproblem{theproblemof
conducting asearchthroughsomeunstructured searchspace{couldalsobespedupon
a quantum computer. WhileGrover’s algorithm did not provide as spectacular a speed-
upasShor’salgorithms,thewidespreadapplicabilityofsearch-basedmethodologies has
excited considerable interest inGrover’salgorithm.
At about the same time as Shor’s and Grover’s algorithms were discovered, many
people were developing anideaRichardFeynman hadsuggestedin1982.Feynman had
pointedoutthatthereseemedtobeessentialdif?cultiesinsimulatingquantum mechan-
ical systems on classical computers, and suggested that building computers based on
the principles of quantum mechanics would allow us to avoid those dif?culties. In the
1990sseveralteamsofresearchers beganeshing thisideaout,showingthat itisindeed
possible to use quantum computers to ef?ciently simulate systems that have no known
ef?cientsimulationonaclassicalcomputer.Itislikelythatoneofthemajorapplications
ofquantumcomputersinthefuturewillbeperformingsimulationsofquantummechan-
ical systems too dif?cult to simulate on a classical computer, a problem with profound
scienti?c andtechnological implications.
Whatother problemscan quantum computers solvemorequicklythan classicalcom-
puters? The short answer is that we don’t know. Coming up with good quantum algo-
rithmsseemstobehard.Apessimistmightthinkthat’sbecausethere’snothingquantum
computers aregoodforotherthan theapplicationsalreadydiscovered!Wetakeadiffer-
ent view. Algorithm design for quantum computers is hard because designers face two
dif?cult problems not faced in the construction of algorithms for classical computers.
First,our human intuitionisrootedintheclassicalworld.Ifweusethat intuitionasan
aid to the construction of algorithms, then the algorithmic ideas we come up with will
beclassicalideas.Todesigngoodquantumalgorithmsonemust‘turnoff’one’sclassical
intuition for at least part of the design process, using truly quantum effects to achieve
thedesiredalgorithmicend.Second,tobetrulyinterestingitisnotenoughtodesignan
algorithm that is merely quantum mechanical. The algorithm must be better than any
existing classical algorithm! Thus, it is possible that one may ?nd an algorithm which
makes use of truly quantum aspects of quantum mechanics, that is nevertheless not of
widespread interest because classical algorithms with comparable performance charac-
teristics exist. The combination of these two problems makes the construction of new
quantum algorithmsachallenging problemforthefuture.
Evenmorebroadly,wecanaskifthereareanygeneralizationswecanmakeaboutthe
powerofquantum computersversusclassicalcomputers.Whatisitthatmakesquantum
computers more powerful than classical computers { assuming that this is indeed the
case? Whatclassofproblemscanbesolvedef?ciently onaquantum computer, andhow
doesthatclasscomparetotheclassofproblemsthatcanbesolvedef?cientlyonaclassical
computer? One of the most exciting things about quantum computation and quantum
information is how little is known about the answers to these questions! It is a great
challenge for the future to understand these questions better.
Having come up to the frontier of quantum computation, let’s switch to the history8 Introductionandoverview
of another strand of thought contributing to quantum computation and quantum infor-
mation: information theory. At the same time computer science was exploding in the
1940s, another revolution was taking place in our understanding of communication.In
1948 Claude Shannon published a remarkable pair of papers laying the foundations for
the modern theory ofinformation and communication.
Perhaps the key steptaken byShannon wastomathematically de?netheconceptof
information.Inmanymathematicalsciencesthereisconsiderableexibilityinthechoice
of fundamental de?nitions. Try thinking naively for a few minutes about the following
question:howwouldyougoaboutmathematically de?ningthenotionofaninformation
source? Severaldifferent answers to this problem have found widespread use; however,
the de?nition Shannon came up with seems to be far and away the most fruitful in
terms of increased understanding, leading to a plethora of deep results and a theory
with a rich structure which seems to accurately reect many (though not all) real-world
communications problems.
Shannon was interested in two key questions related to the communication of in-
formation over a communications channel. First, what resources are required to send
information over a communications channel? For example, telephone companies need
to know how much information they can reliablytransmit over a given telephone cable.
Second, can information be transmitted in such a way that it is protected against noise
inthe communications channel?
Shannon answered these two questions by proving the two fundamental theorems of
information theory. The ?rst, Shannon’s noiseless channel coding theorem, quanti?es
the physical resources required to store the output from an information source. Shan-
non’s second fundamental theorem, the noisy channel coding theorem, quanti?es how
much information it is possible to reliably transmit through a noisy communications
channel. Toachievereliabletransmissioninthepresenceofnoise,Shannonshowedthat
error-correcting codes could be used to protect the information being sent. Shannon’s
noisy channel coding theorem gives an upper limit on the protection afforded by error-
correctingcodes.Unfortunately,Shannon’stheoremdoesnotexplicitlygiveapractically
usefulsetoferror-correctingcodestoachievethatlimit.FromthetimeofShannon’spa-
persuntiltoday,researchershaveconstructedmoreandbetterclassesoferror-correcting
codesintheirattemptstocomeclosertothelimitsetbyShannon’stheorem.Asophisti-
cated theory of error-correcting codes now exists offering the user aplethora of choices
intheirquesttodesignagooderror-correctingcode.Suchcodesareusedinamultitude
of places including, for example, compact disc players, computer modems, and satellite
communications systems.
Quantum information theory has followed with similar developments. In 1995, Ben
Schumacher provided an analogue to Shannon’s noiseless coding theorem, and in the
process de?ned the ‘quantum bit’ or ‘qubit’ as a tangible physical resource. However,
no analogue to Shannon’s noisy channel coding theorem is yet known for quantum in-
formation. Nevertheless, in analogy to their classical counterparts, a theory of quantum
error-correctionhas beendeveloped which, asalready mentioned, allowsquantum com-
puters to compute effectively in the presence of noise, and also allows communication
overnoisyquantum channels to take place reliably.
Indeed, classical ideas of error-correction have proved to be enormously important
in developing and understanding quantum error-correcting codes. In 1996, two groups
workingindependently, RobertCalderbankandPeterShor,andAndrewSteane,discov-Globalperspectives 9
ered an important class of quantum codes now known as CSS codes after their initials.
Thisworkhassincebeensubsumedbythestabilizercodes,independentlydiscoveredby
Robert Calderbank, Eric Rains, Peter Shor and Neil Sloane, and by Daniel Gottesman.
Bybuildinguponthebasicideasofclassicallinearcodingtheory,thesediscoveriesgreatly
facilitatedarapidunderstandingofquantumerror-correctingcodesandtheirapplication
to quantum computation and quantum information.
Thetheoryofquantumerror-correctingcodeswasdevelopedtoprotectquantumstates
against noise. What about transmitting ordinary classical information using a quantum
channel? How ef?ciently can this bedone? A few surprises have been discovered inthis
arena. In 1992 Charles Bennett and Stephen Wiesner explained how to transmit two
classical bits of information, while only transmitting one quantum bit from sender to
receiver, aresult dubbedsuperdense coding.
Even more interesting are the results indistributed quantum computation.Imagine
you have two computers networked, trying to solve a particular problem. How much
communication isrequired to solvethe problem?Recently ithas beenshownthat quan-
tum computers can requireexponentially less communication to solvecertain problems
thanwouldberequiredifthenetworkedcomputers wereclassical!Unfortunately, asyet
these problems are not especially important ina practical setting, and suffer from some
undesirable technical restrictions. A major challenge for the future of quantum compu-
tation and quantum information is to ?nd problems of real-world importance for which
distributedquantumcomputationoffersasubstantialadvantageoverdistributedclassical
computation.
Let’sreturntoinformationtheoryproper.Thestudyofinformationtheorybeginswith
the properties of a single communications channel. In applications we often do not deal
withasinglecommunications channel, butrather withnetworks ofmany channels. The
subjectofnetworkedinformationtheory deals withtheinformationcarryingproperties
of such networks of communications channels, and has been developed into a rich and
intricate subject.
By contrast, the study of networked quantum information theory is very much in its
infancy.Evenforverybasicquestionsweknowlittleabouttheinformationcarryingabil-
ities of networks of quantum channels. Several rather striking preliminary results have
beenfoundinthepastfewyears;however,nounifyingtheoryofnetworkedinformation
theory exists for quantum channels. One example of networked quantum information
theory should suf?ce to convince you of the value such a general theory would have.
ImaginethatweareattemptingtosendquantuminformationfromAlicetoBobthrough
a noisy quantum channel. If that channel has zero capacity for quantum information,
thenitisimpossibletoreliablysendanyinformationfromAlicetoBob.Imagineinstead
thatweconsidertwocopiesofthechannel,operatinginsynchrony.Intuitivelyitisclear
(and canberigorouslyjusti?ed)thatsuchachannel alsohaszerocapacity tosendquan-
tuminformation. However,ifweinsteadreverse the directionofoneofthechannels, as
illustrated in Figure 1.1, it turns out that sometimes we can obtain a non-zero capacity
for the transmissionof informationfrom Aliceto Bob! Counter-intuitive properties like
this illustrate the strange nature of quantum information. Better understanding the in-
formationcarryingpropertiesofnetworksofquantum channels isamajoropenproblem
of quantum computation and quantum information.
Let’sswitch?eldsonelasttime,movingtothe venerableoldartandscience ofcryp-
tography. Broadly speaking, cryptography is the problem of doing communication or10 Introductionandoverview
Figure1.1.Classically, ifwehavetwoverynoisychannelsofzerocapacityrunningsidebyside,thenthecombined
channelhaszerocapacitytosendinformation.Notsurprisingly, ifwereversethedirectionofoneofthechannels,
westill havezerocapacitytosendinformation.Quantummechanically,reversingoneofthezerocapacitychannels
canactuallyallow ustosendinformation!
computation involving two or more parties who may not trust one another.Thebest
knowncryptographicproblemisthetransmissionofsecretmessages.Supposetwoparties
wishtocommunicateinsecret.Forexample,youmaywishtogiveyourcreditcardnum-
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’lldescribeindetailhowcryptographicprotocolsworklaterinthebook,but
fornowitwillsuf?cetomakeafewsimpledistinctions.Themostimportantdistinction
isbetweenprivate keycryptosystems andpublickeycryptosystems.
Thewayaprivatekeycryptosystemworksisthat twoparties,‘Alice’and‘Bob’,wish
tocommunicate bysharingaprivatekey,whichonlytheyknow.Theexactformofthe
key doesn’t matter at this point { think ofa string of zeroes and ones. Thepoint 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
originalinformation.ExactlyhowAliceencrypts themessagedependsupontheprivate
key, sothat to recover theoriginalmessageBob needs to know theprivate key,inorder
to undo the transformation Aliceapplied.
Unfortunately,privatekeycryptosystemshavesomesevereproblemsinmanycontexts.
Themostbasicproblemishowtodistributethekeys?Inmanyways,thekeydistribution
problem is just as dif?cult as the original problem of communicating in private { a
malevolent third party may be eavesdropping on the key distribution, and then use the
intercepted keytodecrypt someof the message transmission.
Oneoftheearliestdiscoveriesinquantumcomputationandquantuminformationwas
thatquantum mechanics canbeusedtodokeydistributioninsuchawaythatAliceand
Bob’ssecurity can not becompromised. Thisprocedure is knownasquantumcryptog-
raphyorquantumkeydistribution.Thebasicideaistoexploitthequantummechanical
principlethatobservationingeneraldisturbsthesystembeingobserved.Thus,ifthereis
aneavesdropperlisteninginasAliceandBobattempttotransmittheirkey,thepresence
oftheeavesdropper willbevisibleasadisturbanceofthecommunications 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 ?rst quantum
cryptographic ideas were proposed by Stephen Wiesner in the late 1960s, but unfortu-Globalperspectives 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 cryptographicprotocolshave beenproposed, andexperimental
prototypesdeveloped.Atthetimeofthiswriting,theexperimentalprototypesarenearing
thestagewherethey maybeuseful inlimited-scalereal-worldapplications.
The second major type of cryptosystem is the public key cryptosystem. Public key
cryptosystems don’trelyonAliceandBob sharingasecret keyinadvance. 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 isextremely dif?cult (though not
impossible)toinvert,givenonlyknowledgeofthepublickey.Tomakeinversioneasy,Bob
has asecretkeymatchedtohispublickey,whichtogetherenablehimtoeasily perform
thedecryption.ThissecretkeyisnotknowntoanybodyotherthanBob,whocantherefore
becon?dentthatonlyhecanreadthecontentsofAlice’stransmission,totheextentthat
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
bymakingitunnecessaryforAliceandBobtoshareaprivatekeybeforecommunicating.
Rather remarkably,publickey cryptography didnotachieve widespread useuntil the
mid-1970s,whenitwasproposedindependentlybyWhit?eldDif?eandMartinHellman,
and by Ralph Merkle, revolutionizing the ?eld 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
offera?nebalanceofsecurityandpracticalusability.In1997itwasdisclosedthatthese
ideas { public key cryptography, the Dif?e{Hellman and RSA cryptosystems { were
actually invented inthe late 1960sandearly1970sbyresearchers workingat the British
intelligence agency GCHQ.
The key to the security of public key cryptosystems is that it should be dif?cult 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.
MuchofthepresumedsecurityofRSAcomesfromthebeliefthatfactoringisaproblem
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 whichcan bebrokenifafast algorithmforsolvingthe 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 ofthe interest inquantum computation and quantum information.
We have been looking at the historical antecedents for quantum computation and
quantum information. Of course, as the ?eld has grown and matured, it has sprouted
itsownsub?eldsofresearch,whoseantecedents liemainlywithinquantumcomputation
and quantum information.
Perhaps the most striking of these is the study ofquantum 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 a12 Introductionandoverview
tremendousefforttryingtobetterunderstandthepropertiesofentanglementconsidered
as a fundamental resource of Nature, of comparable importance to energy, information,
entropy,oranyotherfundamental resource.Althoughthereisasyetnocompletetheory
ofentanglement,someprogresshasbeenmadeinunderstanding thisstrangepropertyof
quantummechanics.Itishopedbymanyresearchersthatfurtherstudyoftheproperties
ofentanglement willyieldinsightsthatfacilitatethedevelopmentofnewapplications in
quantum computation and quantum information.
1.1.2 Futuredirections
We’ve looked at some at 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 bene?ts does
quantumcomputationandquantuminformationconferuponitsparent?eldsofcomputer
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 movingontomore 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
excitingcapabilitiesforinformationprocessingandcommunication.Computerscientists
and information theorists have been gifted with a new and rich paradigm for explo-
ration.Indeed,inthebroadesttermswehavelearnedthatanyphysicaltheory,notjust
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, withconcomitant bene?ts and drawbacks for society as awhole.
Quantum computation and quantum information certainly offer challenges aplenty
to physicists, but it is perhaps a little subtle what quantum computation and quantum
informationofferstophysicsinthelongterm.Webelievethatjustaswehavelearnedto
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
whenthings becomelarger andmorecomplicated. Chemistry andengineering 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 ?elds 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 ofphysics.
We’ve briey examined some of the key motivations and ideas underlying quantum
computation and quantum information. Over the remaining sections of this chapter we
giveamoretechnicalbutstillaccessibleintroductiontothesemotivationsandideas,with
thehopeof givingyouabird’s-eyeview ofthe ?eldasit ispresently poised.Quantumbits 13
1.2 Quantumbits
The bit is the fundamental concept of classical computation and classical information.
Quantum computation and quantum information are built upon an analogous concept,
thequantumbit,orqubitforshort.Inthissectionweintroducetheproperties ofsingle
andmultiplequbits,comparingandcontrastingtheirpropertiestothoseofclassicalbits.
Whatisaqubit? We’regoingtodescribequbitsasmathematical objects withcertain
speci?c properties. ‘But hang on’, you say, ‘I thought qubits were physical objects.’ It’s
truethat qubits,likebits,arerealizedasactual physicalsystems,andinSection1.5and
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
abstractmathematical objects.Thebeautyoftreatingqubitsasabstractentities isthatit
givesusthefreedomtoconstructageneraltheoryofquantumcomputationandquantum
information which does not depend upon a speci?c system for its realization.
What then is a qubit? Just as a classical bit has a state{either0or1{aqubitalso
hasastate.Twopossiblestatesforaqubitarethestatesj0iandj1i,whichasyoumight
guess correspond to the states 0 and 1 for a classical bit. Notation like‘ji’ 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
stateotherthanj0iorj1i.Itisalsopossibletoformlinearcombinations ofstates,often
calledsuperpositions:
j?i= ?j0i+?j1i: (1.1)
The numbers ? and ? are complex numbers, although for many purposes not much is
lostbythinkingofthemasrealnumbers.Putanotherway,thestateofaqubitisavector
in a two-dimensional complex vector space. The special statesj0i andj1i are known as
computational basisstates, and forman orthonormal basisfor thisvector 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
2 2
eithertheresult0,withprobabilityj?j ,ortheresult1,withprobabilityj?j .Naturally,
2 2
j?j +j?j =1,sincetheprobabilitiesmustsumtoone.Geometrically,wecaninterpret
this as the condition that the qubit’s state be normalized to length 1. Thus, ingeneral a
qubit’s state isa unit vector in atwo-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
correspondencewiththe?nalbuilding.Thelackofthisdirectcorrespondenceinquantum
mechanics makes it dif?cult 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 veri?able
consequences,whichweshallseeareessentialtothepowerofquantumcomputationand
quantum information.
14 Introductionandoverview
Theabilityofaqubittobeinasuperpositionstaterunscountertoour‘commonsense’
understanding ofthephysicalworldaroundus.Aclassicalbitislikeacoin:eitherheads
ortailsup. For imperfect coins,there maybeintermediate states likehaving itbalanced
onanedge,butthosecanbedisregardedintheidealcase.Bycontrast,aqubitcanexist
in a continuum of states between j0i and j1i { 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, aqubitcanbeinthe state
1 1
p j0i+p j1i; (1.2)
2 2
p
2
which, when measured, gives the result 0 ?fty percent (j1= 2j)ofthetime,andthe
result 1 ?fty percent of the time. We will return often to this state, which is sometimes
denotedj+i.
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 physicalsystemscan beusedto realizequbits.Togetaconcrete feel forhowa
qubitcanberealizeditmaybehelpfultolistsomeofthewaysthisrealizationmayoccur:
as the two different polarizations of a photon; as the alignment of a nuclear spin in a
uniformmagnetic?eld;astwostatesofanelectronorbitingasingleatomsuchasshown
in Figure 1.2. In the atom model, the electron can exist in either the so-called ‘ground’
or‘excited’states,whichwe’llcallj0iandj1i,respectively.Byshininglightontheatom,
with appropriate energy and for an appropriate length of time, it is possible to move
theelectronfromthej0istatetothej1istateandviceversa.Butmoreinterestingly,by
reducing the time we shine the light, an electron initially in the statej0i can be moved
‘halfway’ betweenj0iandj1i, into thej+istate.
Figure1.2. Qubitrepresentedbytwoelectroniclevelsinanatom.
Naturally, agreatdeal ofattention has beengivento the‘meaning’ or‘interpretation’
thatmightbeattachedtosuperpositionstates,andoftheinherentlyprobabilisticnatureof
observationsonquantumsystems.However,byandlarge,weshallnotconcernourselves
with such discussions in this book. Instead, our intent will be to develop mathematical
and conceptual pictures which are predictive.
Onepictureuseful inthinkingaboutqubitsisthefollowinggeometricrepresentation.
Quantumbits 15
2 2
Becausej?j +j?j =1,we may rewrite Equation (1.1)as
?
i i’
j?i= e cos j0i+e sin j1i ; (1.3)
2 2
where ;’ and arerealnumbers.InChapter2wewillseethatwecanignorethefactor
i
of e out the front, because it has no observable effects, and for that reason we can
effectively write
i’
j?i=cos j0i+e sin j1i: (1.4)
2 2
The numbers and ’de?ne a point on the unit three-dimensional sphere, as shown in
Figure 1.3. This sphere is often called the Bloch sphere; it provides a useful means of
visualizing the state of a single qubit, and often serves as an excellent testbed for ideas
aboutquantumcomputationandquantuminformation.Manyoftheoperationsonsingle
qubitswhichwedescribelaterinthischapterareneatlydescribedwithintheBlochsphere
picture. However, itmust bekept inmind that this intuitionis limitedbecause there is
no simplegeneralization oftheBlochsphereknownformultiplequbits.
|0?
z
j i
y
x
’
|1?
Figure 1.3. Blochsphererepresentationof a qubit.
How much information is represented by a qubit? Paradoxically, there are an in?nite
number of points on the unit sphere, so that in principle one could store an entire text
of Shakespeare in the in?nite binary expansion of . However, this conclusion turns
out to be misleading, because of the behavior of a qubit when observed. Recall that
measurement ofaqubitwillgiveonlyeither0or1.Furthermore, measurementchanges
thestateofaqubit,collapsingitfromitssuperpositionofj0iandj1itothespeci?cstate
consistent with the measurement result. For example, if measurement of j+i gives 0,
then the post-measurement stateofthequbitwillbej0i.Whydoes this typeofcollapse
occur? Nobody knows. As discussed in Chapter 2, this behavior is simply one of the
fundamentalpostulatesofquantummechanics.Whatisrelevantforourpurposesisthat
fromasinglemeasurementoneobtainsonlyasinglebitofinformationaboutthestateof
the qubit, thus resolving the apparent paradox. It turns out that only if in?nitely many16 Introductionandoverview
identically prepared qubits were measured would one be able to determine ? and ? for
aqubit inthe state giveninEquation (1.1).
But an even more interesting question to ask might be: how much information is
represented by a qubit if we do not measure it? This is a trick question, because how
canonequantify informationifitcannot bemeasured? Nevertheless, thereissomething
conceptually important here, because when Nature evolves a closed quantum system of
qubits, not performing any ‘measurements’, she apparently does keep track of all the
continuousvariablesdescribingthestate,like ?and ?.Inasense,inthestateofaqubit,
Natureconcealsagreatdealof‘hiddeninformation’.Andevenmoreinterestingly,wewill
seeshortlythatthepotentialamountofthisextra‘information’growsexponentiallywith
the number of qubits. Understanding this hidden quantum information is a question
that we grapple with for much of this book, and which lies at the heart of what makes
quantum mechanics a powerful tool for information processing.
1.2.1 Multiplequbits
Hilbertspaceisabigplace.
{CarltonCaves
Suppose we have two qubits. If these were two classical bits, then there would be four
possible states, 00, 01, 10, and 11. Correspondingly, a two qubit system has four com-
putational basis states denoted j00i;j01i;j10i;j11i. A pair of qubits can also exist in
superpositionsofthesefourstates,sothequantumstateoftwoqubitsinvolvesassociating
a complex coef?cient { sometimes called an amplitude { with each computational basis
state, such that the state vector describing the two qubits is
j?i= ? j00i+? j01i+? j10i+? j11i: (1.5)
00 01 10 11
Similartothecaseforasinglequbit,themeasurementresultx(=00;01;10or11)occurs
2
withprobabilityj? j ,withthestateofthequbitsafterthemeasurementbeingjxi.The
x
condition that probabilities sum to one is therefore expressed by the normalization
P
2 2
conditionthat j? j =1,wherethenotation‘f0;1g ’means ‘thesetofstrings
2
x
x2f0;1g
oflengthtwowitheachletterbeingeitherzeroorone’.Foratwoqubitsystem,wecould
measure justasubset of the qubits,say the ?rst qubit,and youcan probablyguess how
2 2
thisworks:measuringthe?rstqubitalonegives0withprobabilityj? j +j? j,leaving
00 01
the post-measurement state
? j00i+? j01i
00 01
0
j?i= p : (1.6)
2 2
j? j +j? j
00 01
p
2 2
Note how the post-measurement state is re-normalized by the factor j? j +j? j
00 01
so that it still satis?es the normalization condition, just as we expect for a legitimate
quantum state.
An important two qubitstate is theBellstateorEPRpair,
j00i+j11i
p : (1.7)
2
Thisinnocuous-lookingstateisresponsibleformanysurprisesinquantum computation
Quantumcomputation 17
and quantum information. It is the key ingredient in quantum teleportation and super-
dense coding, which we’ll come to in Section 1.3.7 and Section 2.3, respectively, and
theprototypeformanyotherinterestingquantum states.TheBellstatehastheproperty
that upon measuring the ?rst qubit, one obtains two possibleresults: 0 withprobability
0
1=2,leavingthepost-measurement statej’i=j00i,and1withprobability1=2,leaving
0
j’i=j11i.Asaresult,ameasurement ofthesecond qubitalwaysgivesthesameresult
asthemeasurementofthe?rstqubit.Thatis,themeasurementoutcomesarecorrelated.
Indeed, it turns out that other types of measurements can be performed on the Bell
state, by ?rst applying some operations to the ?rst or second qubit, and that interesting
correlationsstillexistbetweentheresultofameasurementonthe?rstandsecondqubit.
These correlations have been the subject of intense interest ever since a famous paper
by Einstein, Podolsky and Rosen, in which they ?rst pointed out the strange properties
of states likethe Bell state. EPR’sinsights weretaken upand greatly improvedby John
Bell, who proved an amazing result: the measurement correlations in the Bell state are
strongerthancouldeverexistbetweenclassicalsystems.Theseresults,describedinde-
tail inSection 2.6,werethe ?rstintimationthat quantum mechanics allowsinformation
processing beyondwhatispossibleintheclassical world.
Moregenerally,wemayconsiderasystemof nqubits.Thecomputationalbasisstates
of this system are of the form jx x :::x i, and so a quantum state of such a system
1 2 n
n
is speci?ed by 2 amplitudes. For n = 500 this number is larger than the estimated
number ofatoms inthe Universe!Tryingtostoreallthese complex numbers wouldnot
be possible on any conceivable classical computer. Hilbert space is indeed a big place.
In principle, however, Nature manipulates such enormous quantities of data, even for
500
systemscontainingonlyafewhundredatoms.ItisasifNaturewerekeeping2 hidden
piecesofscratchpaperontheside,onwhichsheperformshercalculationsasthesystem
evolves.Thisenormouspotentialcomputationalpowerissomethingwewouldverymuch
liketo take advantage of. But how can we think of quantum mechanics as computation?
1.3 Quantumcomputation
Changes occurring to a quantum state can be described using the language ofquantum
computation.Analogoustothewayaclassicalcomputerisbuiltfromanelectricalcircuit
containing wires and logic gates, a quantum computer is built from a quantum circuit
containing wires and elementary quantum gates to carry around and manipulate the
quantuminformation.Inthissectionwedescribesomesimplequantumgates,andpresent
several examplecircuitsillustratingtheir application, including acircuitwhichteleports
qubits!
1.3.1 Singlequbitgates
Classical computer circuits consist ofwires andlogicgates.Thewiresareusedto carry
informationaroundthecircuit,whilethelogicgatesperformmanipulationsoftheinfor-
mation,convertingitfromoneformtoanother.Consider,forexample,classicalsinglebit
logic gates. The only non-trivial member of this class is the gate, whose operation
is de?ned by itstruth table,inwhich0!1and1! 0, that is, the 0 and 1 states are
interchanged.
Can an analogous quantum gate for qubits be de?ned? Imagine that we had
some process which took the state j0i to the state j1i, and vice versa. Such a process
18 Introductionandoverview
wouldobviouslybeagoodcandidateforaquantumanaloguetothe gate.However,
specifyingtheactionofthegateonthestatesj0iandj1idoesnottelluswhathappensto
superpositions of the statesj0i andj1i, without further knowledge about the properties
ofquantum gates. In fact, the quantum gate actslinearly, that is, ittakes the state
?j0i+?j1i (1.8)
tothecorresponding stateinwhichtheroleofj0iandj1ihave beeninterchanged,
?j1i+?j0i: (1.9)
Why the quantum gate acts linearly and not in some nonlinear fashion is a very
interesting question, and the answer is not at all obvious. It turns out that this linear
behaviorisageneralpropertyofquantummechanics,andverywellmotivatedempirically;
moreover,nonlinear behaviorcan lead to apparent paradoxes suchas timetravel, faster-
than-light communication, and violations of the second laws of thermodynamics. We’ll
explorethispointinmoredepthinlaterchapters,butfornowwe’lljusttakeitasgiven.
There is a convenient way of representing the quantum gate in matrix form,
which follows directly from the linearity of quantum gates. Suppose we de?ne a matrix
X to represent the quantum gate asfollows:
? ?
01
X · : (1.10)
10
(The notation X for the quantum is used for historical reasons.) If the quantum
state ?j0i+?j1iiswritten ina vector notation as
? ?
?
; (1.11)
?
with the top entry corresponding to the amplitude for j0i and the bottom entry the
amplitude forj1i, then the corresponding output from the quantum gate is
? ? ? ?
? ?
X = : (1.12)
? ?
Notice that the action of the gate is to take the statej0i and replace it by the state
correspondingtothe?rstcolumnofthematrix X.Similarly,thestatej1iisreplacedby
the state corresponding to the second column of the matrix X.
Soquantumgatesonasinglequbitcanbedescribedbytwobytwomatrices.Arethere
any constraints on what matrices may be used as quantum gates? It turns out that there
2 2
are.Recall that thenormalizationconditionrequiresj?j +j?j =1 for a quantum state
0 0 0
?j0i+ ?j1i. This must also be true of the quantum statej?i = ?j0i+ ?j1i after the
gatehasacted. Itturnsoutthattheappropriateconditiononthematrixrepresenting the
y
gate is that the matrix U describing the single qubit gate beunitary,thatisU U = I,
y
where U is the adjoint of U (obtained by transposing and then complex conjugating
U),and I is thetwo bytwo identity matrix.For example, for the gateitiseasy to
y
verify that X X = I.
Amazingly, this unitarity constraint is the only constraint on quantum gates. Any
unitary matrix speci?es a valid quantum gate! The interesting implication is that in
contrast to the classical case, where onlyone non-trivialsinglebitgate exists {the
Quantumcomputation 19
|0?
z z z
y y y
x x x
01 +
2
|1?
p
Figure1.4. VisualizationoftheHadamardgateontheBlochsphere,actingontheinputstate(j0i+j1i)= 2.
gate{therearemanynon-trivialsinglequbitgates.Twoimportantoneswhichweshall
use later arethe Z gate:
? ?
10
Z · ; (1.13)
0 ?1
which leavesj0i unchanged, and ips the sign of j1i to give?j1i,andtheHadamard
gate,
? ?
1 11
p
H · : (1.14)
1 ?1
2
Thisgateissometimesdescribedasbeinglikea‘square-rootof ’gate,inthatitturns
p
a j0i into (j0i+j1i)= 2 (?rst column of H), ‘halfway’ between j0i and j1i,andturns
p
j1i into (j0i?j1i)= 2 (second column of H), which is also ‘halfway’ between j0i and
2 2
j1i.Note,however,thatH isnota gate,assimplealgebrashowsthat H = I,and
thus applying Htwicetoastatedoesnothingtoit.
TheHadamardgateisoneofthemostusefulquantumgates,anditisworthtryingto
visualize its operation by considering the Bloch sphere picture. In this picture, it turns
out that single qubit gates correspond to rotations and reections of the sphere. The
–
Hadamard operation isjustarotationofthesphereaboutthe y^ axisby90 ,followedby
a reection through the x^-y^ plane, as illustrated in Figure 1.4. Some important single
qubit gates areshown inFigure 1.5,and contrasted withthe classical case.
xx
Figure1.5. Single bit (left)andqubit (right)logic gates.
Therearein?nitelymanytwobytwounitarymatrices,andthusin?nitelymanysingle
20 Introductionandoverview
qubit gates. However, it turns out that the properties of the complete set can beunder-
stood from the properties of a much smaller set. For example, as explained in Box 1.1,
an arbitrary singlequbitunitary gate can be decomposed as a product of rotations
? ?
cos ?sin
2 2
; (1.15)
sin cos
2 2
and a gate which we’lllater understand as being a rotation aboutthe z^ axis,
? ?
?i?=2
e 0
; (1.16)
i?=2
0 e
i?
togetherwitha(global)phaseshift{aconstantmultiplieroftheform e .Thesegates
can be broken down further { we don’t need to be able to do these gates for arbitrary
?;?and ,butcanbuildarbitrarilygoodapproximationstosuchgatesusingonlycertain
special?xedvaluesof ?;?and .Inthiswayitispossibletobuildupanarbitrarysingle
qubit gate using a ?nite set of quantum gates. More generally, an arbitrary quantum
computationonanynumberofqubitscanbegeneratedbya?nitesetofgatesthatissaid
to be universal for quantum computation. To obtain such a universal set we ?rst need
to introduce somequantum gates involvingmultiple qubits.
Box1.1:Decomposingsinglequbitoperations
InSection 4.2starting on page 174we prove that an arbitrary2￡2 unitary matrix
may bedecomposed as
? ?? ? ? ?
?i?=2 ?i–=2
e 0 cos ?sin e 0
i?
2 2
U = e ; ; (1.17)
i?=2 i–=2
0 e sin cos 0 e
2 2
where ?, ?, ,and– are real-valued. Notice that the second matrix is just an
ordinaryrotation.Itturnsoutthatthe?rstandlastmatricescanalsobeunderstood
as rotations in a different plane. This decomposition can be used to give an exact
prescription for performing anarbitrary singlequbit quantum logicgate.
1.3.2 Multiplequbitgates
Nowletusgeneralizefromonetomultiplequbits.Figure1.6shows?venotablemultiple
bitclassicalgates,the , , (exclusive- ), and gates.Animportant
theoretical result is that any function on bits can be computed from the composition of
gatesalone,whichisthusknownasauniversalgate.Bycontrast,the aloneor
even together with is notuniversal. Oneway ofseeing this is to note that applying
an gatedoesnotchangethetotalparityofthebits.Asaresult,anycircuitinvolving
only and gates will, if two inputs x and y have the same parity, give outputs
withthesameparity,restrictingtheclassoffunctionswhichmaybecomputed,andthus
precluding universality.
Theprototypicalmulti-qubitquantumlogicgateisthecontrolled- or gate.
Thisgatehastwoinputqubits,knownasthecontrolqubitandthetargetqubit,respec-
tively. The circuit representation for the is shown in the top right of Figure 1.6;
the top line represents the control qubit, while the bottom line represents the target
|
|
