Contents - Volume I
Preface
Introduction
1. Introduction to Classical Computation
1.1 The Turing machine
1.1.1 Addition on a Turing machine
1.1.2 The Church-Turing thesis
1.1.3 The universal Turing machine
1.1.4 The probabilistic Turing machine
1.1.5 * The halting problem
1.2 The circuit model of computation
1.2.1 Binary arithmetics
1.2.2 Elementary logic gates
1.2.3 Universal classical computation
1.3 Computational complexity
1.3.1 Complexity classes
1.3.2 * The Chernoff bound
1.4 * Computing of dynamical systems
1.4.1 * Deterministic chaos
1.4.2 * Algorithmic complexity
1.5 Energy and information
1.5.1 Maxwell's demon
1.5.2 Landauer's principle
1.5.3 Extracting work from information
1.6 Reversible computation
1.6.1 Toffoli and Fredkin gates
1.6.2 * The billiard-ball computer
1.7 A guide to the bibliography
2. Introduction to Quantum
Mechanics
2.1 The Stern-Gerlach experiment
2.2 Young's double-slit experiment
2.3 Linear vector spaces
2.4 The postulates of quantum mechanics
2.5 The EPR paradox and Bell's
inequalities
2.6 A guide to the bibliography
3. Quantum Computation
3.1 The qubit
3.1.1 The Bloch sphere
3.1.2 Measuring the state of a qubit
3.2 The circuit model of quantum
computation
3.3 Single-qubit gates
3.3.1 Rotations of the Bloch sphere
3.4 Controlled gates and entanglement
generation
3.4.1 The Bell basis
3.5 Universal quantum gates
3.5.1 * Preparation of the initial state
3.6 Unitary errors
3.7 Function evaluation
3.8 The quantum adder
3.9 Deutsch's algorithm
3.9.1 The Deutsch-Jozsa problem
3.9.2 * An extension of Deutsch's algorithm
3.10 Quantum search
3.10.1 Searching one item out of four
3.10.2 Searching
one item out of N
3.10.3 Geometric visualization
3.11 The quantum Fourier transform
3.12 Quantum phase estimation
3.13 * Finding eigenvalues and
eigenvectors
3.14 Period finding and Shor's algorithm
3.15 Quantum computation of dynamical
systems
3.15.1 Quantum simulation of the Schrodinger equation
3.15.2 * The quantum baker's map
3.15.3 * The quantum sawtooth map
3.15.4 * Quantum computation of dynamical localization
3.16 First experimental implementations
3.16.1 Elementary gates with spin qubits
3.16.2 Overview of the first implementations
3.17 A guide to the bibliography
3. Quantum Communication
4.1 Classical cryptography
4.1.1 The
Vernam cypher
4.1.2 The
public-key cryptosystem
4.1.3 The
RSA protocol
4.2 The no-cloning theorem
4.2.1
Faster-than-light transmission of information?
4.3 Quantum cryptography
4.3.1 The
BB84 protocol
4.3.2 The
E91 protocol
4.4 Dense coding
4.5 Quantum teleportation
4.6 An overview of the
experimental implementations
4.7 A guide to the bibliography
Appendix A. Solutions to
the exercises
Bibliography
Index