PRINCIPLES OF QUANTUM COMPUTATION AND INFORMATION: BASIC CONCEPTS
CONTENTS INTRODUCTION 1 1 INTRODUCTION TO CLASSICAL COMPUTATION 9 1 1 THE TURING MACHINE 9 1 1 1 ADDITION ON A TURING MACHINE 11 1 1 2 THE CHURCH TURING THESIS 13 1 1 3 THE UNIVERSAL TURING MACHINE 14 1 1 4 THE PROBABILISTIC TURING MACHINE 15 1 1 5 THE HALTING PROBLEM 15 1 2 THE CIRCUIT MODEL OF COMPUTATION 16 1 2 1 BINARY ARITHMETICS 17 1 2 2 ELEMENTARY LOGIC GATES 18 1 2 3 UNIVERSAL CLASSICAL COMPUTATION 21 1 3 COMPUTATIONAL COMPLEXITY 22 1 3 1 TRACTABLE VS INTRACTABLE PROBLEMS 23 1 3 2 COMPLEXITY CLASSES 30 1 3 3 THE CHERNO BOUND 34 1 4 COMPUTING DYNAMICAL SYSTEMS 34 1 4 1 DETERMINISTIC CHAOS 35 1 4 2 ALGORITHMIC COMPLEXITY 37 1 5 ENERGY AND INFORMATION 39 1 5 1 MAXWELL S DEMON 39 1 5 2 LANDAUER S PRINCIPLE 40 1 5 3 EXTRACTING WORK FROM INFORMATION 42 1 6 REVERSIBLE COMPUTATION 43 1 6 1 TO OLI AND FREDKIN GATES 45 1 6 2 THE BILLIARD BALL COMPUTER 46 1 7 ENERGY DISSIPATION IN COMPUTATION 48 1 7 1 EXPERIMENTAL REALIZATION OF A MAXWELL S DEMON 48 1 7 2 EXPERIMENTAL VERI CATION OF LANDAUER S PRINCIPLE 49 1 7 3 ENERGY DISSIPATION IN REAL CLASSICAL COMPUTER 50 1 7 4 EXPERIMENTAL REALIZATION OF REVERSIBLE COMPUTERS 51 1 7 5 NEUROMOR C COMPUTING 53 1 8 A GUIDE TO THE BIBLIOGRAPHY 54 2 INTRODUCTION TO QUANTUM MECHANICS 55 2 1 THE STERN GERLACH EXPERIMENT 56 2 2 YOUNG S DOUBLE SLIT EXPERIMENT 59 2 3 THE POSTULATES OF QUANTUM MECHANICS 63 2 3 1 DYNAMICAL EVOLUTION 63 2 3 2 OUTCOMES OF A MEASUREMENT 64 2 3 3 THE POST MEASUREMENT STATE 67 2 3 4 HEISENBERG S UNCERTAINTY PRINCIPLE 69 2 4 THE EPR PARADOX 72 2 5 BELL S INEQUALITIES 77 2 6 THE DENSITY MATRIX 81 2 6 1 COMPOSITE SYSTEMS 86 2 7 THE SCHMIDT DECOMPOSITION 89 2 8 PURI CATION 91 2 9 GENERALIZED MEASUREMENTS 93 2 9 1 POVM MEASUREMENTS 94 2 10 A GUIDE TO THE BIBLIOGRAPHY 96 3 QUANTUM COMPUTATION 97 3 1 THE QUBIT 98 3 1 1 PURE QUBIT STATES THE BLOCH SPHERE 99 3 1 2 MIXED QUBIT STATES THE BLOCH BALL 100 3 2 MEASURING THE STATE OF A QUBIT 103 3 2 1 PURE QUBIT STATES 103 3 2 2 MIXED QUBIT STATES 104 3 3 THE CIRCUIT MODEL OF QUANTUM COMPUTATION 105 3 4 SINGLE QUBIT GATES 108 3 4 1 ROTATIONS OF THE BLOCH SPHERE 109 3 5 CONTROLLED GATES AND ENTANGLEMENT GENERATION 111 3 5 1 THE BELL BASIS 115 3 6 HAMILTONIAN MODEL FOR ONE AND TWO QUBIT GATES 116 3 7 UNIVERSAL QUANTUM GATES 117 3 7 1 PREPARATION OF THE INITIAL STATE 124 3 8 UNITARY ERRORS 127 3 9 FUNCTION EVALUATION 128 3 10 THE QUANTUM ADDER 132 3 11 ADIABATIC THEOREM 134 3 11 1 ADIABATIC CONDITION 136 3 11 2 BERRY PHASE 137 3 12 NON ABELIAN GEOMETRIC PHASE 141 3 13 ADIABATIC QUANTUM COMPUTATION 145 3 14 MAXIMUM SPEED OF QUANTUM GATES 149 3 14 1 SPEED LIMIT OF AN AUTONOMOUS TIME EVOLUTION 150 3 14 2 SPEED LIMIT OF SINGLE QUBIT GATES 151 3 15 HOLONOMIC QUANTUM COMPUTATION 152 3 16 A GUIDE TO THE BIBLIOGRAPHY 155 4 QUANTUM ALGORITHMS 157 4 1 DEUTSCH S ALGORITHM 157 4 1 1 THE DEUTSCH JOZSA PROBLEM 158 4 1 2 AN EXTENSION OF DEUTSCH S ALGORITHM 159 4 2 QUANTUM SEARCH 161 4 2 1 SEARCHING ONE ITEM OUT OF FOUR 161 4 2 2 SEARCHING ONE ITEM OUT OF N 163 4 2 3 GEOMETRIC VISUALIZATION 164 4 2 4 SEARCHING BY ADIABATIC QUANTUM EVOLUTION 166 4 3 THE QUANTUM FOURIER TRANSFORM 168 4 4 QUANTUM PHASE ESTIMATION 171 4 5 FINDING EIGENVALUES AND EIGENVECTORS 173 4 6 PERIOD NDING AND SHOR S ALGORITHM 175 4 7 QUANTUM COMPUTATION OF DYNAMICAL SYSTEMS 179 4 7 1 QUANTUM SIMULATION OF THE SCHR ODINGER EQUATION 179 4 7 2 THE QUANTUM BAKER S MAP 183 4 7 3 THE QUANTUM SAWTOOTH MAP 185 4 7 4 INFORMATION EXTRACTION FOR DYNAMICAL QUANTUM SYSTEMS 188 4 8 UNIVERSAL QUANTUM SIMULATION 190 4 9 A GUIDE TO THE BIBLIOGRAPHY 192 5 QUANTUM COMMUNICATION 195 5 1 CLASSICAL CRYPTOGRAPHY 195 5 1 1 THE VERNAM CYPHER 196 5 1 2 THE PUBLIC KEY CRYPTOSYSTEM 197 5 1 3 THE RSA PROTOCOL 198 5 2 THE NO CLONING THEOREM 199 5 2 1 FASTER THAN LIGHT TRANSMISSION OF INFORMATION 201 5 2 2 THE NO SIGNALLING CONDITION 203 5 2 3 UNIVERSAL QUANTUM CLONING 204 5 2 4 THE UNIVERSAL NOT GATE 206 5 3 QUANTUM CRYPTOGRAPHY 207 5 3 1 THE BB84 PROTOCOL 207 5 3 2 THE E91 PROTOCOL 210 5 4 DENSE CODING 212 5 5 QUANTUM TELEPORTATION 215 5 5 1 CONCLUSIVE TELEPORTATION 219 5 6 QUANTUM MECHANICS WITH CONTINUOUS VARIABLES 220 5 6 1 GENERAL FRAMEWORK FOR GAUSSIAN STATES 233 5 7 QUANTUM CRYPTOGRAPHY WITH CONTINUOUS VARIABLES 237 5 8 A GUIDE TO THE BIBLIOGRAPHY 240 6 ENTANGLEMENT AND NON CLASSICAL CORRELATIONS 241 6 1 DE NITION OF ENTANGLEMENT 241 6 1 1 BASIC PROPERTIES 242 6 2 BIPARTITE SEPARABILITY CRITERIA 243 6 2 1 THE PERES SEPARABILITY CRITERION 244 6 2 2 POSITIVE MAPS 245 6 2 3 ENTANGLEMENT WITNESSES 246 6 2 4 POSITIVE MAPS AND WITNESSES 248 6 3 THE SHANNON ENTROPY 248 6 3 1 MUTUAL INFORMATION 250 6 4 THE VON NEUMANN ENTROPY 252 6 4 1 EXAMPLE 1 SOURCE OF ORTHOGONAL PURE STATES 255 6 4 2 EXAMPLE 2 SOURCE OF NON ORTHOGONAL PURE STATES 255 6 5 ENTANGLEMENT CONCENTRATION 256 6 5 1 ENTANGLEMENT OF A RANDOM STATE 260 6 6 REQUIREMENTS FOR BIPARTITE ENTANGLEMENT MEASURES 263 6 7 OTHER ENTANGLEMENT MEASURES 264 6 7 1 CONCURRENCE 264 6 7 2 NEGATIVITY 265 6 8 MULTIPARTITE ENTANGLEMENT 266 6 8 1 MONOGAMY OF ENTANGLEMENT AND TANGLE MEASURES 268 6 9 QUANTUM DISCORD 269 6 9 1 DE NITION 270 6 9 2 BASIC PROPERTIES 273 6 9 3 EXAMPLES 274 6 9 4 OTHER MEASURES OF QUANTUM CORRELATIONS 275 6 10 QUANTUM DISCORD IN CONTINUOUS SYSTEMS 277 6 10 1 ENTROPY OF A GAUSSIAN STATE 277 6 10 2 DISCORD OF A GAUSSIAN STATE 278 6 11 ENTROPIES IN PHYSICS 279 6 11 1 THERMODYNAMIC ENTROPY 280 6 11 2 STATISTICAL ENTROPY 282 6 11 3 DYNAMICAL KOLMOGOROV SINAI ENTROPY 284 6 12 A GUIDE TO THE BIBLIOGRAPHY 285 7 DECOHERENCE 287 7 1 THE KRAUS REPRESENTATION 287 7 2 DECOHERENCE MODELS FOR A SINGLE QUBIT 293 7 2 1 THE QUANTUM BLACK BOX 294 7 2 2 MEASURING A QUANTUM OPERATION ACTING ON A QUBIT 295 7 2 3 QUANTUM CIRCUITS SIMULATING NOISE CHANNELS 296 7 2 4 THE BIT IP CHANNEL 298 7 2 5 THE PHASE IP CHANNEL 299 7 2 6 THE BIT PHASE IP CHANNEL 300 7 2 7 THE DEPOLARIZING CHANNEL 301 7 2 8 AMPLITUDE DAMPING 302 7 2 9 PHASE DAMPING 303 7 2 10 DE ENTANGLEMENT 305 7 3 THE BLOCH FANO REPRESENTATION 307 7 3 1 BLOCH FANO REPRESENTATION OF A STATE 307 7 3 2 BLOCH FANO REPRESENTATION OF A QUANTUM OPERATION 308 7 4 THE MASTER EQUATION 310 7 4 1 DERIVATION OF THE MASTER EQUATION 311 7 4 2 THE MASTER EQUATION AND QUANTUM OPERATIONS 319 7 4 3 THE MASTER EQUATION FOR A SINGLE QUBIT 322 7 5 NON MARKOVIAN QUANTUM DYNAMICS 324 7 6 QUANTUM TO CLASSICAL TRANSITION 329 7 6 1 SCHR ODINGER S CAT 329 7 6 2 DECOHERENCE AND DESTRUCTION OF CAT STATES 330 7 7 DECOHERENCE AND QUANTUM MEASUREMENTS 335 7 7 1 WEAK MEASUREMENTS 337 7 7 2 DECOHERENCE AND QUANTUM TRAJECTORIES 340 7 8 A GUIDE TO THE BIBLIOGRAPHY 344 8 QUANTUM INFORMATION THEORY 345 8 1 CLASSICAL DATA COMPRESSION 346 8 1 1 SHANNON S NOISELESS CODING THEOREM 346 8 1 2 EXAMPLES OF DATA COMPRESSION 348 8 1 3 CAPACITY OF CLASSICAL CHANNELS 349 8 2 QUANTUM DATA COMPRESSION 351 8 2 1 SCHUMACHER S QUANTUM NOISELESS CODING THEOREM 351 8 2 2 COMPRESSION OF AN N QUBIT MESSAGE 352 8 2 3 EXAMPLE 1 TWO QUBIT MESSAGES 354