本书分三大部分。

第1部分为总论和量子物理学基础，还包括少量计算机科学基础知识。量子物理学基础部分主要介绍学习量子计算与量子信息所必需的量子力学基础知识，这一部分採用了侧重于数学框架和公理化体系的讲述方法，从而更便于为非物理专业的读者所理解。

第2部分讲述量子计算，包括量子算法和实现量子算法的一些物理系统的基础内容。这部分首先介绍了实现普适量子计算所需要的基本逻辑门——单量子比特门与条件非门（第4章）。之后较详细地介绍了现有的两个主要量子算法问题，即质因数分解问题（第5章）和搜寻问题（第6章）。第7章讲物理实现，介绍了几个主要的实现条件非门的物理系统；这些物理系统虽然目前尚未实现大规模量子计算，但是大多数已经实现或基本实现了普适量子计算所需要的基本逻辑门。

第3部分为量子资讯理论，主要介绍量子纠错码和量子资讯理论的数学框架。这里包括了非常重要的量子密码的基础内容，即理想条件下的安全性证明（第12.6节）。第3部分未包含物理实现内容。

量子信息处理可以带来许多意想不到的具有特殊优势的结果。量子算法可以有效地进行大数质因数分解。在量子算法背景下，很多经典保密通信协定的安全性受到威胁，然而量子保密通信可以抵抗来自包括量子计算机在内的任何针对通道的攻击。由于存在诸多特殊套用，量子计算与量子信息科学近年来得到蓬勃发展。

对于这一相对年轻但又具有广阔发展前景的学科，优秀的系统化的教材比较缺乏。本书是本领域公认的最权威的系统化教材之一，也几乎是本学科研究人员的必备基本材料，有学者曾将之称为量子计算与量子信息学科教材中的“圣经”。

本书的特点是全面包含量子计算和量子信息的核心内容，且系统性强，结构清晰，深入浅出。这使其很适合作为相关专业的本科生和研究生教材，也适合于用作本领域研究人员的基础参考资料；对于那些準备从其他研究领域转行投入本领域研究的具有物理学、信息科学或数学等专业背景的研究人员，本书也是一本非常合适的入门书籍。

如同任何其他书籍一样，本书的内容也不可能面面俱到。本书几乎未涉及连续变数量子信息处理的有关内容。这方面，目前有多篇综述论文和一些专门教材可供参考。另外，儘管同多数同类教材比较起来，本书已经较深入地介绍了量子密码内容，但是相比于其重要性，量子密码方面的内容量还是有些偏少，对这方面感兴趣的读者可参阅相关专着。

王向斌

清华大学物理系

2015年9月

PartI

Fundamentalconcepts1

1Introductionandoverview1

1.1Globalperspectives1

1.1.1Historyofquantumcomputationandquantuminformation2

1.1.2Futuredirections12

1.2Quantumbits13

1.2.1Multiplequbits16

1.3Quantumcomputation17

1.3.1Singlequbitgates17

1.3.2Multiplequbitgates20

1.3.3Measurementsinbasesotherthanthecomputationalbasis22

1.3.4Quantumcircuits22

1.3.5Qubitcopyingcircuit?24

1.3.6Example:Bellstates25

1.3.7Example:quantumteleportation26

1.4Quantumalgorithms28

1.4.1Classicalcomputationsonaquantumcomputer29

1.4.2Quantumparallelism30

1.4.3Deutsch’salgorithm32

1.4.4TheDeutsch–Jozsaalgorithm34

1.4.5Quantumalgorithmssummarized36

1.5Experimentalquantuminformationprocessing42

1.5.1TheStern–Gerlachexperiment43

1.5.2Prospectsforpracticalquantuminformationprocessing46

1.6Quantuminformation50

1.6.1Quantuminformationtheory:exampleproblems52

1.6.2Quantuminformationinawidercontext58

2Introductiontoquantummechanics60

2.1Linearalgebra61

2.1.1Basesandlinearindependence62

2.1.2Linearoperatorsandmatrices63

2.1.3ThePaulimatrices65

2.1.4Innerproducts65

2.1.5Eigenvectorsandeigenvalues68

2.1.6AdjointsandHermitianoperators69

2.1.7Tensorproducts71

2.1.8Operatorfunctions75

2.1.9Thecommutatorandanti-commutator76

2.1.10Thepolarandsingularvaluedecompositions78

2.2Thepostulatesofquantummechanics80

2.2.1Statespace80

2.2.2Evolution81

2.2.3Quantummeasurement84

2.2.4Distinguishingquantumstates86

2.2.5Projectivemeasurements87

2.2.6POVMmeasurements90

2.2.7Phase93

2.2.8Compositesystems93

2.2.9Quantummechanics:aglobalview96

2.3Application:superdensecoding97

2.4Thedensityoperator98

2.4.1Ensemblesofquantumstates99

2.4.2Generalpropertiesofthedensityoperator101

2.4.3Thereduceddensityoperator105

2.5TheSchmidtdecompositionandpurifications109

2.6EPRandtheBellinequality111

3Introductiontocomputerscience120

3.1Modelsforcomputation122

3.1.1Turingmachines122

3.1.2Circuits129

3.2Theanalysisofcomputationalproblems135

3.2.1Howtoquantifycomputationalresources136

3.2.2Computationalcomplexity138

3.2.3DecisionproblemsandthecomplexityclassesPandNP141

3.2.4Aplethoraofcomplexityclasses150

3.2.5Energyandcomputation153

3.3Perspectivesoncomputerscience161

PartIIQuantumcomputation171

4Quantumcircuits171

4.1Quantumalgorithms172

4.2Singlequbitoperations174

4.3Controlledoperations177

4.4Measurement185

4.5Universalquantumgates188

4.5.1Two-levelunitarygatesareuniversal189

4.5.2SinglequbitandCNOTgatesareuniversal191

4.5.3Adiscretesetofuniversaloperations194

4.5.4Approximatingarbitraryunitarygatesisgenericallyhard198

4.5.5Quantumcomputationalcomplexity200

4.6Summaryofthequantumcircuitmodelofcomputation202

4.7Simulationofquantumsystems204

4.7.1Simulationinaction204

4.7.2Thequantumsimulationalgorithm206

4.7.3Anillustrativeexample209

4.7.4Perspectivesonquantumsimulation211

5ThequantumFouriertransformanditsapplications216

5.1ThequantumFouriertransform217

5.2Phaseestimation221

5.2.1Performanceandrequirements223

5.3Applications:order-findingandfactoring226

5.3.1Application:order-finding226

5.3.2Application:factoring232

5.4GeneralapplicationsofthequantumFouriertransform234

5.4.1Period-finding236

5.4.2Discretelogarithms238

5.4.3Thehiddensubgroupproblem240

5.4.4Otherquantumalgorithms?242

6Quantumsearchalgorithms248

6.1Thequantumsearchalgorithm248

6.1.1Theoracle248

6.1.2Theprocedure250

6.1.3Geometricvisualization252

6.1.4Performance253

6.2Quantumsearchasaquantumsimulation255

6.3Quantumcounting261

6.4SpeedingupthesolutionofNP-completeproblems263

6.5Quantumsearchofanunstructureddatabase265

6.6Optimalityofthesearchalgorithm269

6.7Blackboxalgorithmlimits271

7Quantumcomputers:physicalrealization277

7.1Guidingprinciples277

7.2Conditionsforquantumcomputation279

7.2.1Representationofquantuminformation279

7.2.2Performanceofunitarytransformations281

7.2.3Preparationoffiducialinitialstates281

7.2.4Measurementofoutputresult282

7.3Harmonicoscillatorquantumcomputer283

7.3.1Physicalapparatus283

7.3.2TheHamiltonian284

7.3.3Quantumcomputation286

7.3.4Drawbacks286

7.4Opticalphotonquantumcomputer287

7.4.1Physicalapparatus287

7.4.2Quantumcomputation290

7.4.3Drawbacks296

7.5Opticalcavityquantumelectrodynamics297

7.5.1Physicalapparatus298

7.5.2TheHamiltonian300

7.5.3Single-photonsingle-atomabsorptionandrefraction303

7.5.4Quantumcomputation306

7.6Iontraps309

7.6.1Physicalapparatus309

7.6.2TheHamiltonian317

7.6.3Quantumcomputation319

7.6.4Experiment321

7.7Nuclearmagneticresonance324

7.7.1Physicalapparatus325

7.7.2TheHamiltonian326

7.7.3Quantumcomputation331

7.7.4Experiment336

7.8Otherimplementationschemes343

PartIIIQuantuminformation353

8Quantumnoiseandquantumoperations353

8.1ClassicalnoiseandMarkovprocesses354

8.2Quantumoperations356

8.2.1Overview356

8.2.2Environmentsandquantumoperations357

8.2.3Operator-sumrepresentation360

8.2.4Axiomaticapproachtoquantumoperations366

8.3Examplesofquantumnoiseandquantumoperations373

8.3.1Traceandpartialtrace374

8.3.2Geometricpictureofsinglequbitquantumoperations374

8.3.3Bitflipandphaseflipchannels376

8.3.4Depolarizingchannel378

8.3.5Amplitudedamping380

8.3.6Phasedamping383

8.4Applicationsofquantumoperations386

8.4.1Masterequations386

8.4.2Quantumprocesstomography389

8.5Limitationsofthequantumoperationsformalism394

9Distancemeasuresforquantuminformation399

9.1Distancemeasuresforclassicalinformation399

9.2Howclosearetwoquantumstates?403

9.2.1Tracedistance403

9.2.2Fidelity409

9.2.3Relationshipsbetweendistancemeasures415

9.3Howwelldoesaquantumchannelpreserveinformation?416

10Quantumerror-correction425

10.1Introduction426

10.1.1Thethreequbitbitflipcode427

10.1.2Threequbitphaseflipcode430

10.2TheShorcode432

10.3Theoryofquantumerror-correction435

10.3.1Discretizationoftheerrors438

10.3.2Independenterrormodels441

10.3.3Degeneratecodes444

10.3.4ThequantumHammingbound444

10.4Constructingquantumcodes445

10.4.1Classicallinearcodes445

10.4.2Calderbank–Shor–Steanecodes450

10.5Stabilizercodes453

10.5.1Thestabilizerformalism454

10.5.2Unitarygatesandthestabilizerformalism459

10.5.3Measurementinthestabilizerformalism463

10.5.4TheGottesman–Knilltheorem464

10.5.5Stabilizercodeconstructions464

10.5.6Examples467

10.5.7Standardformforastabilizercode470

10.5.8Quantumcircuitsforencoding,decoding,andcorrection472

10.6Fault-tolerantquantumcomputation474

10.6.1Fault-tolerance:thebigpicture475

10.6.2Fault-tolerantquantumlogic482

10.6.3Fault-tolerantmeasurement489

10.6.4Elementsofresilientquantumcomputation493

11Entropyandinformation500

11.1Shannonentropy500

11.2Basicpropertiesofentropy502

11.2.1Thebinaryentropy502

11.2.2Therelativeentropy504

11.2.3Conditionalentropyandmutualinformation505

11.2.4Thedataprocessinginequality509

11.3VonNeumannentropy510

11.3.1Quantumrelativeentropy511

11.3.2Basicpropertiesofentropy513

11.3.3Measurementsandentropy514

11.3.4Subadditivity515

11.3.5Concavityoftheentropy516

11.3.6Theentropyofamixtureofquantumstates518

11.4Strongsubadditivity519

11.4.1Proofofstrongsubadditivity519

11.4.2Strongsubadditivity:elementaryapplications522

12Quantuminformationtheory528

12.1Distinguishingquantumstatesandtheaccessibleinformation529

12.1.1TheHolevobound531

12.1.2ExampleapplicationsoftheHolevobound534

12.2Datacompression536

12.2.1Shannon’snoiselesschannelcodingtheorem537

12.2.2Schumacher’squantumnoiselesschannelcodingtheorem542

12.3Classicalinformationovernoisyquantumchannels546

12.3.1Communicationovernoisyclassicalchannels548

12.3.2Communicationovernoisyquantumchannels554

12.4Quantuminformationovernoisyquantumchannels561

12.4.1EntropyexchangeandthequantumFanoinequality561

12.4.2Thequantumdataprocessinginequality564

12.4.3QuantumSingletonbound568

12.4.4Quantumerror-correction,refrigerationandMaxwell’sdemon569

12.5Entanglementasaphysicalresource571

12.5.1Transformingbi-partitepurestateentanglement573

12.5.2Entanglementdistillationanddilution578

12.5.3Entanglementdistillationandquantumerror-correction580

12.6Quantumcryptography582

12.6.1Privatekeycryptography582

12.6.2Privacyamplificationandinformationreconciliation584

12.6.3Quantumkeydistribution586

12.6.4Privacyandcoherentinformation592

12.6.5Thesecurityofquantumkeydistribution593

Appendices608

Appendix1:Notesonbasicprobabilitytheory608

Appendix2:Grouptheory610

A2.1Basicdefinitions610

A2.1.1Generators611

A2.1.2Cyclicgroups611

A2.1.3Cosets612

A2.2Representations612

A2.2.1Equivalenceandreducibility612

A2.2.2Orthogonality613

A2.2.3Theregularrepresentation614

A2.3Fouriertransforms615

Appendix3:TheSolovay--Kitaevtheorem617

Appendix4:Numbertheory625

A4.1Fundamentals625

A4.2ModulararithmeticandEuclid’salgorithm626

A4.3Reductionoffactoringtoorder-finding633

A4.4Continuedfractions635

Appendix5:PublickeycryptographyandtheRSAcryptosystem640

Appendix6:ProofofLieb’stheorem645

Bibliography649

Index

665