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