You are previewing Quantum Computation and Quantum Information.
O'Reilly logo
Quantum Computation and Quantum Information

Book Description

One of the most cited books in physics of all time, Quantum Computation and Quantum Information remains the best textbook in this exciting field of science. This 10th anniversary edition includes an introduction from the authors setting the work in context. This comprehensive textbook describes such remarkable effects as fast quantum algorithms, quantum teleportation, quantum cryptography and quantum error-correction. Quantum mechanics and computer science are introduced before moving on to describe what a quantum computer is, how it can be used to solve problems faster than 'classical' computers and its real-world implementation. It concludes with an in-depth treatment of quantum information. Containing a wealth of figures and exercises, this well-known textbook is ideal for courses on the subject, and will interest beginning graduate students and researchers in physics, computer science, mathematics, and electrical engineering.

Table of Contents

  1. Cover
  2. Title
  3. Copyright
  4. Contents
  5. Introduction to the Tenth Anniversary Edition
  6. Afterword to the Tenth Anniversary Edition
  7. Preface
  8. Acknowledgement
  9. Nomenclature
  10. Part I Fundamental concepts
    1. 1 Introduction and overview
      1. 1.1 Global perspectives
        1. 1.1.1 History of quantum computation and quantum information
        2. 1.1.2 Future directions
      2. 1.2 Quantum bits
        1. 1.2.1 Multiple qubits
      3. 1.3 Quantum computation
        1. 1.3.1 Single qubit gates
        2. 1.3.2 Multiple qubit gates
        3. 1.3.3 Measurements in bases other than the computational basis
        4. 1.3.4 Quantum circuits
        5. 1.3.5 Qubit copying circuit?
        6. 1.3.6 Example: Bell states
        7. 1.3.7 Example: quantum teleportation
      4. 1.4 Quantum algorithms
        1. 1.4.1 Classical computations on a quantum computer
        2. 1.4.2 Quantum parallelism
        3. 1.4.3 Deutsch's algorithm
        4. 1.4.4 The Deutsch–Jozsa algorithm
        5. 1.4.5 Quantum algorithms summarized
      5. 1.5 Experimental quantum information processing
        1. 1.5.1 The Stern–Gerlach experiment
        2. 1.5.2 Prospects for practical quantum information processing
      6. 1.6 Quantum information
        1. 1.6.1 Quantum information theory: example problems
        2. 1.6.2 Quantum information in a wider context
    2. 2 Introduction to quantum mechanics
      1. 2.1 Linear algebra
        1. 2.1.1 Bases and linear independence
        2. 2.1.2 Linear operators and matrices
        3. 2.1.3 The Pauli matrices
        4. 2.1.4 Inner products
        5. 2.1.5 Eigenvectors and eigenvalues
        6. 2.1.6 Adjoints and Hermitian operators
        7. 2.1.7 Tensor products
        8. 2.1.8 Operator functions
        9. 2.1.9 The commutator and anti-commutator
        10. 2.1.10 The polar and singular value decompositions
      2. 2.2 The postulates of quantum mechanics
        1. 2.2.1 State space
        2. 2.2.2 Evolution
        3. 2.2.3 Quantum measurement
        4. 2.2.4 Distinguishing quantum states
        5. 2.2.5 Projective measurements
        6. 2.2.6 POVM measurements
        7. 2.2.7 Phase
        8. 2.2.8 Composite systems
        9. 2.2.9 Quantum mechanics: a global view
      3. 2.3 Application: superdense coding
      4. 2.4 The density operator
        1. 2.4.1 Ensembles of quantum states
        2. 2.4.2 General properties of the density operator
        3. 2.4.3 The reduced density operator
      5. 2.5 The Schmidt decomposition and purifications
      6. 2.6 EPR and the Bell inequality
    3. 3 Introduction to computer science
      1. 3.1 Models for computation
        1. 3.1.1 Turing machines
        2. 3.1.2 Circuits
      2. 3.2 The analysis of computational problems
        1. 3.2.1 How to quantify computational resources
        2. 3.2.2 Computational complexity
        3. 3.2.3 Decision problems and the complexity classes P and NP
        4. 3.2.4 A plethora of complexity classes
        5. 3.2.5 Energy and computation
      3. 3.3 Perspectives on computer science
  11. Part II Quantum computation
    1. 4 Quantum circuits
      1. 4.1 Quantum algorithms
      2. 4.2 Single qubit operations
      3. 4.3 Controlled operations
      4. 4.4 Measurement
      5. 4.5 Universal quantum gates
        1. 4.5.1 Two-level unitary gates are universal
        2. 4.5.2 Single qubit and CNOT gates are universal
        3. 4.5.3 A discrete set of universal operations
        4. 4.5.4 Approximating arbitrary unitary gates is generically hard
        5. 4.5.5 Quantum computational complexity
      6. 4.6 Summary of the quantum circuit model of computation
      7. 4.7 Simulation of quantum systems
        1. 4.7.1 Simulation in action
        2. 4.7.2 The quantum simulation algorithm
        3. 4.7.3 An illustrative example
        4. 4.7.4 Perspectives on quantum simulation
    2. 5 The quantum Fourier transform and its applications
      1. 5.1 The quantum Fourier transform
      2. 5.2 Phase estimation
        1. 5.2.1 Performance and requirements
      3. 5.3 Applications: order-finding and factoring
        1. 5.3.1 Application: order-finding
        2. 5.3.2 Application: factoring
      4. 5.4 General applications of the quantum Fourier transform
        1. 5.4.1 Period-finding
        2. 5.4.2 Discrete logarithms
        3. 5.4.3 The hidden subgroup problem
        4. 5.4.4 Other quantum algorithms?
    3. 6 Quantum search algorithms
      1. 6.1 The quantum search algorithm
        1. 6.1.1 The oracle
        2. 6.1.2 The procedure
        3. 6.1.3 Geometric visualization
        4. 6.1.4 Performance
      2. 6.2 Quantum search as a quantum simulation
      3. 6.3 Quantum counting
      4. 6.4 Speeding up the solution of NP-complete problems
      5. 6.5 Quantum search of an unstructured database
      6. 6.6 Optimality of the search algorithm
      7. 6.7 Black box algorithm limits
    4. 7 Quantum computers: physical realization
      1. 7.1 Guiding principles
      2. 7.2 Conditions for quantum computation
        1. 7.2.1 Representation of quantum information
        2. 7.2.2 Performance of unitary transformations
        3. 7.2.3 Preparation of fiducial initial states
        4. 7.2.4 Measurement of output result
      3. 7.3 Harmonic oscillator quantum computer
        1. 7.3.1 Physical apparatus
        2. 7.3.2 The Hamiltonian
        3. 7.3.3 Quantum computation
        4. 7.3.4 Drawbacks
      4. 7.4 Optical photon quantum computer
        1. 7.4.1 Physical apparatus
        2. 7.4.2 Quantum computation
        3. 7.4.3 Drawbacks
      5. 7.5 Optical cavity quantum electrodynamics
        1. 7.5.1 Physical apparatus
        2. 7.5.2 The Hamiltonian
        3. 7.5.3 Single-photon single-atom absorption and refraction
        4. 7.5.4 Quantum computation
      6. 7.6 Ion traps
        1. 7.6.1 Physical apparatus
        2. 7.6.2 The Hamiltonian
        3. 7.6.3 Quantum computation
        4. 7.6.4 Experiment
      7. 7.7 Nuclear magnetic resonance
        1. 7.7.1 Physical apparatus
        2. 7.7.2 The Hamiltonian
        3. 7.7.3 Quantum computation
        4. 7.7.4 Experiment
      8. 7.8 Other implementation schemes
  12. Part III Quantum information
    1. 8 Quantum noise and quantum operations
      1. 8.1 Classical noise and Markov processes
      2. 8.2 Quantum operations
        1. 8.2.1 Overview
        2. 8.2.2 Environments and quantum operations
        3. 8.2.3 Operator-sum representation
        4. 8.2.4 Axiomatic approach to quantum operations
      3. 8.3 Examples of quantum noise and quantum operations
        1. 8.3.1 Trace and partial trace
        2. 8.3.2 Geometric picture of single qubit quantum operations
        3. 8.3.3 Bit flip and phase flip channels
        4. 8.3.4 Depolarizing channel
        5. 8.3.5 Amplitude damping
        6. 8.3.6 Phase damping
      4. 8.4 Applications of quantum operations
        1. 8.4.1 Master equations
        2. 8.4.2 Quantum process tomography
      5. 8.5 Limitations of the quantum operations formalism
    2. 9 Distance measures for quantum information
      1. 9.1 Distance measures for classical information
      2. 9.2 How close are two quantum states?
        1. 9.2.1 Trace distance
        2. 9.2.2 Fidelity
        3. 9.2.3 Relationships between distance measures
      3. 9.3 How well does a quantum channel preserve information?
    3. 10 Quantum error-correction
      1. 10.1 Introduction
        1. 10.1.1 The three qubit bit flip code
        2. 10.1.2 Three qubit phase flip code
      2. 10.2 The Shor code
      3. 10.3 Theory of quantum error-correction
        1. 10.3.1 Discretization of the errors
        2. 10.3.2 Independent error models
        3. 10.3.3 Degenerate codes
        4. 10.3.4 The quantum Hamming bound
      4. 10.4 Constructing quantum codes
        1. 10.4.1 Classical linear codes
        2. 10.4.2 Calderbank–Shor–Steane codes
      5. 10.5 Stabilizer codes
        1. 10.5.1 The stabilizer formalism
        2. 10.5.2 Unitary gates and the stabilizer formalism
        3. 10.5.3 Measurement in the stabilizer formalism
        4. 10.5.4 The Gottesman–Knill theorem
        5. 10.5.5 Stabilizer code constructions
        6. 10.5.6 Examples
        7. 10.5.7 Standard form for a stabilizer code
        8. 10.5.8 Quantum circuits for encoding, decoding, and correction
      6. 10.6 Fault-tolerant quantum computation
        1. 10.6.1 Fault-tolerance: the big picture
        2. 10.6.2 Fault-tolerant quantum logic
        3. 10.6.3 Fault-tolerant measurement
        4. 10.6.4 Elements of resilient quantum computation
    4. 11 Entropy and information
      1. 11.1 Shannon entropy
      2. 11.2 Basic properties of entropy
        1. 11.2.1 The binary entropy
        2. 11.2.2 The relative entropy
        3. 11.2.3 Conditional entropy and mutual information
        4. 11.2.4 The data processing inequality
      3. 11.3 Von Neumann entropy
        1. 11.3.1 Quantum relative entropy
        2. 11.3.2 Basic properties of entropy
        3. 11.3.3 Measurements and entropy
        4. 11.3.4 Subadditivity
        5. 11.3.5 Concavity of the entropy
        6. 11.3.6 The entropy of a mixture of quantum states
      4. 11.4 Strong subadditivity
        1. 11.4.1 Proof of strong subadditivity
        2. 11.4.2 Strong subadditivity: elementary applications
    5. 12 Quantum information theory
      1. 12.1 Distinguishing quantum states and the accessible information
        1. 12.1.1 The Holevo bound
        2. 12.1.2 Example applications of the Holevo bound
      2. 12.2 Data compression
        1. 12.2.1 Shannon's noiseless channel coding theorem
        2. 12.2.2 Schumacher's quantum noiseless channel coding theorem
      3. 12.3 Classical information over noisy quantum channels
        1. 12.3.1 Communication over noisy classical channels
        2. 12.3.2 Communication over noisy quantum channels
      4. 12.4 Quantum information over noisy quantum channels
        1. 12.4.1 Entropy exchange and the quantum Fano inequality
        2. 12.4.2 The quantum data processing inequality
        3. 12.4.3 Quantum Singleton bound
        4. 12.4.4 Quantum error-correction, refrigeration and Maxwell's demon
      5. 12.5 Entanglement as a physical resource
        1. 12.5.1 Transforming bi-partite pure state entanglement
        2. 12.5.2 Entanglement distillation and dilution
        3. 12.5.3 Entanglement distillation and quantum error-correction
      6. 12.6 Quantum cryptography
        1. 12.6.1 Private key cryptography
        2. 12.6.2 Privacy amplification and information reconciliation
        3. 12.6.3 Quantum key distribution
        4. 12.6.4 Privacy and coherent information
        5. 12.6.5 The security of quantum key distribution
  13. Appendices
    1. Appendix 1: Notes on basic probability theory
    2. Appendix 2: Group theory
      1. A2.1 Basic definitions
        1. A2.1.1 Generators
        2. A2.1.2 Cyclic groups
        3. A2.1.3 Cosets
      2. A2.2 Representations
        1. A2.2.1 Equivalence and reducibility
        2. A2.2.2 Orthogonality
        3. A2.2.3 The regular representation
      3. A2.3 Fourier transforms
    3. Appendix 3: The Solovay–Kitaev theorem
    4. Appendix 4: Number theory
      1. A4.1 Fundamentals
      2. A4.2 Modular arithmetic and Euclid's algorithm
      3. A4.3 Reduction of factoring to order-finding
      4. A4.4 Continued fractions
    5. Appendix 5: Public key cryptography and the RSA cryptosystem
    6. Appendix 6: Proof of Lieb's theorem
  14. Bibliography
  15. Index