Principles of Quantum Computation and Information - Volume II: Basic Tools and Special Topics

✍ Scribed by Giuliano Benenti, Giulio Casati, Giuliano Strini

• Publisher: World Scientifific
• Year: 2004
• Tongue: English
• Leaves: 445
• Category: Library

✦ Table of Contents

Preface ix
Introduction 1
1. Introduction to Classical Computation 9
1.1 TheTuringmachine ...................... 9 1.1.1 AdditiononaTuringmachine............. 12 1.1.2 TheChurch–Turingthesis ............... 13 1.1.3 TheuniversalTuringmachine............. 14 1.1.4 TheprobabilisticTuringmachine . . . . . . . . . . . 14 1.1.5 ⋆Thehaltingproblem ................. 15
1.2 Thecircuitmodelofcomputation............... 15 1.2.1 Binaryarithmetics ................... 17 1.2.2 Elementarylogicgates ................. 17 1.2.3 Universal classical computation . . . . . . . . . . . . 22
1.3 Computationalcomplexity................... 24 1.3.1 Complexityclasses ................... 27 1.3.2 ⋆TheChernoffbound ................. 30
1.4 ⋆Computingdynamicalsystems ............... 30 1.4.1 ⋆Deterministicchaos.................. 31 1.4.2 ⋆Algorithmiccomplexity................ 33
1.5 Energyandinformation .................... 35 1.5.1 Maxwell’sdemon .................... 35 1.5.2 Landauer’sprinciple .................. 37 1.5.3 Extractingworkfrominformation. . . . . . . . . . . 40
1.6 Reversiblecomputation .................... 41
2.
1.6.1 ToffoliandFredkingates................ 43
1.6.2 ⋆Thebilliard-ballcomputer.............. 45 1.7 Aguidetothebibliography .................. 47
Introduction to Quantum Mechanics 49
2.1 TheStern–Gerlachexperiment ................ 50 2.2 Young’sdouble-slitexperiment ................ 53 2.3 Linearvectorspaces ...................... 57 2.4 Thepostulatesofquantummechanics . . . . . . . . . . . . 76 2.5 TheEPRparadoxandBell’sinequalities. . . . . . . . . . . 88 2.6 Aguidetothebibliography .................. 97
Quantum Computation 99
3.1Thequbit............................ 100 3.1.1 TheBlochsphere.................... 102 3.1.2 Measuringthestateofaqubit. . . . . . . . . . . . . 103
3.2 The circuit model of quantum computation . . . . . . . . . 105
3.3 Single-qubitgates........................ 108 3.3.1 RotationsoftheBlochsphere . . . . . . . . . . . . . 110
3.4 Controlled gates and entanglement generation . . . . . . . . 112 3.4.1 TheBellbasis...................... 118
3.5 Universalquantumgates.................... 118 3.5.1 ⋆ Preparationoftheinitialstate. . . . . . . . . . . . 127
3.6 Unitaryerrors.......................... 130
3.7 Functionevaluation ...................... 132
3.8 Thequantumadder ...................... 137
3.9 Deutsch’salgorithm ...................... 140 3.9.1 TheDeutsch–Jozsaproblem.............. 141 3.9.2 ⋆ An extension of Deutsch’s algorithm . . . . . . . . 143
3.10Quantumsearch ........................ 144 3.10.1Searchingoneitemoutoffour............. 145 3.10.2SearchingoneitemoutofN.............. 147 3.10.3Geometricvisualization ................ 149 3.11ThequantumFouriertransform. . . . . . . . . . . . . . . . 152 3.12Quantumphaseestimation .................. 155 3.13⋆ Finding eigenvalues and eigenvectors . . . . . . . . . . . . 158 3.14PeriodfindingandShor’salgorithm . . . . . . . . . . . . . 161 3.15 Quantum computation of dynamical systems . . . . . . . . 164
3.15.1 Quantum simulation of the Schro ̈dinger equation . . 164 3.15.2⋆Thequantumbaker’smap.............. 168 3.15.3⋆Thequantumsawtoothmap............. 170
3.15.4 ⋆ Quantum computation of dynamical localization 3.16First experimental implementations . . . . . . . . . . . . . 3.16.1 Elementarygateswithspinqubits . . . . . . . . . 3.16.2 Overview of the first implementations . . . . . . .
. 174 . 178 . 179 . 181
3.17Aguidetothebibliography .................. 185
4. Quantum Communication 189
4.1 Classicalcryptography..................... 189 4.1.1 TheVernamcypher................... 190 4.1.2 Thepublic-keycryptosystem . . . . . . . . . . . . . 191 4.1.3 TheRSAprotocol ................... 192
4.2 Theno-cloningtheorem .................... 194
4.2.1 Faster-than-light transmission of information? . . . . 197
4.3 Quantumcryptography .................... 198 4.3.1 TheBB84protocol................... 199 4.3.2 TheE91protocol.................... 202
4.4 Densecoding .......................... 204
4.5 Quantumteleportation..................... 208
4.6 An overview of the experimental implementations . . . . . . 213
4.7 Aguidetothebibliography .................. 214
Appendix A
Bibliography Index
Solutions to the exercises 215 241 253