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

Preface     ix
Introduction     1
Introduction to Classical Computation     9
The Turing machine     9
Addition on a Turing machine     12
The Church-Turing thesis     13
The universal Turing machine     14
The probabilistic Turing machine     14
The halting problem     15
The circuit model of computation     15
Binary arithmetics     17
Elementary logic gates     17
Universal classical computation     22
Computational complexity     24
Complexity classes     27
The Chernoff bound     30
Computing dynamical systems     30
Deterministic chaos     31
Algorithmic complexity     33
Energy and information     35
Maxwell's demon     35
Landauer's principle     37
Extracting work from information     40
Reversible computation     41
Toffoli and Fredkin gates     43
The billiard-ball computer     45
A guide to the bibliography     47
Introduction to Quantum Mechanics     49
The Stern-Gerlach experiment     50
Young's double-slit experiment     53
Linear vector spaces     57
The postulates of quantum mechanics     76
The EPR paradox and Bell's inequalities     88
A guide to the bibliography     97
Quantum Computation     99
The qubit     100
The Bloch sphere     102
Measuring the state of a qubit     103
The circuit model of quantum computation     105
Single-qubit gates     108
Rotations of the Bloch sphere     110
Controlled gates and entanglement generation     112
The Bell basis     118
Universal quantum gates     118
Preparation of the initial state     127
Unitary errors     130
Function evaluation     132
The quantum adder     137
Deutsch's algorithm     140
The Deutsch-Jozsa problem     141
An extension of Deutsch's algorithm     143
Quantum search     144
Searching one item out of four     145
Searching one item out of N     147
Geometric visualization     149
The quantum Fourier transform     152
Quantum phase estimation      155
Finding eigenvalues and eigenvectors     158
Period finding and Shor's algorithm     161
Quantum computation of dynamical systems     164
Quantum simulation of the Schrodinger equation     164
The quantum baker's map     168
The quantum sawtooth map     170
Quantum computation of dynamical localization     174
First experimental implementations     178
Elementary gates with spin qubits     179
Overview of the first implementations     181
A guide to the bibliography     185
Quantum Communication     189
Classical cryptography     189
The Vernam cypher     190
The public-key cryptosystem     191
The RSA protocol     192
The no-cloning theorem     194
Faster-than-light transmission of information?     197
Quantum cryptography     198
The BB84 protocol     199
The E91 protocol     202
Dense coding     204
Quantum teleportation     208
An overview of the experimental implementations     213
A guide to the bibliography     214
Solutions to the exercises      215
Bibliography     241
Index     253