Quantum_Computation and Quantum Information

Quantum_Computation and Quantum Information screenshot

Text-only Preview

This page intentionally left blank

Quantum Computation and Quantum Information
10th Anniversary Edition
One of the most cited books in physics of all time, Quantum Computation and Quantum
remains the best textbook in this exciting field of science. This 10th
Anniversary Edition includes a new Introduction and Afterword 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.
MICHAEL NIELSEN was educated at the University of Queensland, and as a Fulbright
Scholar at the University of New Mexico. He worked at Los Alamos National
Laboratory, as the Richard Chace Tolman Fellow at Caltech, was Foundation Professor
of Quantum Information Science and a Federation Fellow at the University of
Queensland, and a Senior Faculty Member at the Perimeter Institute for Theoretical
Physics. He left Perimeter Institute to write a book about open science and now lives in
ISAAC CHUANG is a Professor at the Massachusetts Institute of Technology, jointly
appointed in Electrical Engineering & Computer Science, and in Physics. He leads the
quanta research group at the Center for Ultracold Atoms, in the MIT Research
Laboratory of Electronics, which seeks to understand and create information technology
and intelligence from the fundamental building blocks of physical systems, atoms, and

In praise of the book 10 years after publication
Ten years after its initial publication, "Mike and Ike" (as it's affectionately called) remains the quantum
computing textbook to which all others are compared. No other book in the field matches its scope:
from experimental implementation to complexity classes, from the philosophical justifications for the
Church-Turing Thesis to the nitty-gritty of bra/ket manipulation. A dog-eared copy sits on my desk;
the section on trace distance and fidelity alone has been worth many times the price of the book to me.
Scott Aaronson, Massachusetts Institute of Technology
Quantum information processing has become a huge interdisciplinary field at the intersection of both,
theoretical and experimental quantum physics, computer science, mathematics, quantum engineering
and, more recently, even quantum metrology. The book by Michael Nielsen and Isaac Chuang was
seminal in many ways: it paved the way for a broader, yet deep understanding of the underlying
science, it introduced a common language now widely used by a growing community and it became
the standard book in the field for a whole decade. In spite of the fast progress in the field, even after
10 years the book provides the basic introduction into the field for students and scholars alike and
the 10th anniversary edition will remain a bestseller for a long time to come. The foundations of
quantum computation and quantum information processing are excellently laid out in this book and
it also provides an overview over some experimental techniques that have become the testing ground
for quantum information processing during the last decade. In view of the rapid progress of the field
the book will continue to be extremely valuable for all entering this highly interdisciplinary research
area and it will always provide the reference for those who grew up with it. This is an excellent book,
well written, highly commendable, and in fact imperative for everybody in the field.
Rainer Blatt, Universtitat Innsbruck
My well-perused copy of Nielsen and Chuang is, as always, close at hand as I write this. It appears
that the material that Mike and Ike chose to cover, which was a lot, has turned out to be a large portion
of what will become the eternal verities of this still-young field. When another researcher asks me to
give her a clear explanation of some important point of quantum information science, I breathe a sigh
of relief when I recall that it is in this book - my job is easy, I just send her there.
David DiVincenzo, IBM T. J. Watson Research Center
If there is anything you want to know, or remind yourself, about quantum information science, then
look no further than this comprehensive compendium by Ike and Mike. Whether you are an expert, a
student or a casual reader, tap into this treasure chest of useful and well presented information.
Artur Ekert, Mathematical Institute, University of Oxford
Nearly every child who has read Harry Potter believes that if you just say the right thing or do the
right thing, you can coerce matter to do something fantastic. But what adult would believe it? Until
quantum computation and quantum information came along in the early 1990s, nearly none. The
quantum computer is the Philosopher's Stone of our century, and Nielsen and Chuang is our basic
book of incantations. Ten years have passed since its publication, and it is as basic to the field as it
ever was. Matter will do wonderful things if asked to, but we must first understand its language. No
book written since (there was no before) does the job of teaching the language of quantum theory's
possibilities like Nielsen and Chuang's.
Chris Fuchs, Perimeter Institute for Theoretical Physics
Nielsen and Chuang is the bible of the quantum information field. It appeared 10 years ago, yet even
though the field has changed enormously in these 10 years - the book still covers most of the important
concepts of the field.
Lov Grover, Bell Labs
Quantum Computation and Quantum Information, commonly referred to as "Mike and Ike," continues
to be a most valuable resource for background information on quantum information processing. As a
mathematically-impaired experimentalist, I particularly appreciate the fact that armed with a modest
background in quantum mechanics, it is possible to pick up at any point in the book and readily grasp
the basic ideas being discussed. To me, it is still "the" book on the subject.
David Wineland, National Institute of Standards and Technology, Boulder, Colorado

Endorsements for the original publication
Chuang and Nielsen have produced the first comprehensive study of quantum computation. To
develop a robust understanding of this subject one must integrate many ideas whose origins are
variously within physics, computer science, or mathematics. Until this text, putting together the
essential material, much less mastering it, has been a challenge. Our Universe has intrinsic capa-
bilities and limitations on the processing of information. What these are will ultimately determine
the course of technology and shape our efforts to find a fundamental physical theory. This book is
an excellent way for any scientist or graduate student - in any of the related fields - to enter the
Michael Freedman, Fields Medalist, Microsoft
Nielsen and Chuang's new text is remarkably thorough and up-to-date, covering many aspects
of this rapidly evolving field from a physics perspective, complementing the computer science
perspective of Gruska's 1999 text. The authors have succeeded in producing a self-contained book
accessible to anyone with a good undergraduate grounding in math, computer science or physical
sciences. An independent student could spend an enjoyable year reading this book and emerge ready
to tackle the current literature and do serious research. To streamline the exposition, footnotes have
been gathered into short but lively History and Further Reading sections at the end of each chapter.
Charles H Bennett, IBM
This is an excellent book. The field is already too big to cover completely in one book, but Nielsen
and Chuang have made a good selection of topics, and explain the topics they have chosen very
Peter Shor, Massachusetts Institute of Technology

Quantum Computation and Quantum Information
10th Anniversary Edition
Michael A. Nielsen & Isaac L. Chuang

Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore,
Sao Paulo, Delhi, Dubai, Tokyo, Mexico City
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
Information on this title: www.cambridge.org/9781107002173
C M. Nielsen and I. Chuang 2010
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2000
Reprinted 2002, 2003, 2004, 2007, 2009
10th Anniversary edition published 2010
Printed in the United Kingdom at the University Press, Cambridge
A catalog record for this publication is available from the British Library
ISBN 978-1-107-00217-3 Hardback
Cambridge University Press has no responsibility for the persistence or
accuracy of URLs for external or third-party internet websites referred to in
this publication, and does not guarantee that any content on such websites is,
or will remain, accurate or appropriate.

To our parents,
and our teachers

Document Outline

  • Cover
  • Half-title
  • Series-title
  • Title
  • Copyright
  • Dedication
  • Contents
  • Introduction to the Tenth Anniversary Edition
  • Afterword to the Tenth Anniversary Edition
    • ﾿
    • Linear algebra and quantum mechanics
    • Information theory and probability
    • Miscellanea
    • Frequently used quantum gates and circuit symbols
  • ﾿
        • ﾿
          • Any algorithmic process can be simulated efficiently using a Turing machine
          • Any algorithmic process can be simulated efficiently using a probabilistic Turing machine
        • 1.2.1 Multiple qubits
      • ﾿
        • 1.3.1 Single qubit gates
        • 1.3.2 Multiple qubit gates
        • 1.3.3 Measurements in bases other than the computational basis
        • 1.3.4 Quantum circuits
        • 1.3.5 Qubit copying circuit?
        • 1.3.6 Example: Bell states
        • 1.3.7 Example: quantum teleportation
        • 1.4.1 Classical computations on a quantum computer
        • 1.4.2 Quantum parallelism
        • 1.4.3 Deutschs algorithm
        • 1.4.4 The DeutschJozsa algorithm
        • 1.4.5 Quantum algorithms summarized
          • Quantum algorithms based upon the Fourier transform
          • Quantum search algorithms
          • Quantum simulation
          • The power of quantum computation
      • ž
        • 1.5.1 The SternGerlach experiment
        • 1.5.2 Prospects for practical quantum information processing
        • 1.6.1 Quantum information theory: example problems
          • Classical information through quantum channels
          • Quantum information through quantum channels
          • Quantum distinguishability
        • 1.6.2 Quantum information in a wider context
      • ﾿
      • 2.1 Linear algebra
        • 2.1.1 Bases and linear independence
        • 2.1.2 Linear operators and matrices
        • 2.1.3 The Pauli matrices
        • 2.1.4 Inner products
        • 2.1.5 Eigenvectors and eigenvalues
        • 2.1.6 Adjoints and Hermitian operators
        • 2.1.7 Tensor products
        • 2.1.8 Operator functions
        • 2.1.9 The commutator and anti-commutator
        • 2.1.10 The polar and singular value decompositions
        • 2.2.1 State space
        • 2.2.2 Evolution
        • 2.2.3 Quantum measurement
        • 2.2.4 Distinguishing quantum states
        • 2.2.5 Projective measurements
        • 2.2.6 POVM measurements
        • 2.2.7 Phase
        • 2.2.8 Composite systems
        • 2.2.9 Quantum mechanics: a global view
      • ﾿
        • 2.4.1 Ensembles of quantum states
        • 2.4.2 General properties of the density operator
        • 2.4.3 The reduced density operator
      • 2.5 The Schmidt decomposition and purifications
      • ﾿
        • 3.1.1 Turing machines
        • 3.1.2 Circuits
      • ﾿
        • 3.2.1 How to quantify computational resources
          • Asymptotic notation: examples
        • 3.2.2 Computational complexity
        • 3.2.3 Decision problems and the complexity classes P and NP
  • ﾿
      • ﾿
      • ﾿
        • 4.5.1 Two-level unitary gates are universal
        • 4.5.2 Single qubit and CNOT gates are universal
        • 4.5.3 A discrete set of universal operations
          • Approximating unitary operators
          • Universality of Hadamard + phase
        • 4.5.4 Approximating arbitrary unitary gates is generically hard
        • 4.5.5 Quantum computational complexity
      • þ
      • ﾿
        • 4.7.1 Simulation in action
        • 4.7.2 The quantum simulation algorithm
        • 4.7.3 An illustrative example
        • 4.7.4 Perspectives on quantum simulation
      • ﾿
        • 5.2.1 Performance and requirements
      • 5.3 Applications: order-finding and factoring
        • 5.3.1 Application: order-finding
          • The continued fraction expansion
          • Performance
        • 5.3.2 Application: factoring
        • 5.4.1 Period-finding
        • 5.4.2 Discrete logarithms
        • 5.4.3 The hidden subgroup problem
        • 5.4.4 Other quantum algorithms?
      • ﾿
        • 6.1.1 The oracle
        • 6.1.2 The procedure
        • 6.1.3 Geometric visualization
        • 6.1.4 Performance
      • ﾿
      • 6.4 Speeding up the solution of NP-complete problems
      • ﾿
      • History and further reading
      • ﾿
        • 7.2.1 Representation of quantum information
        • 7.2.2 Performance of unitary transformations
        • 7.2.3 Preparation of fiducial initial states
        • 7.2.4 Measurement of output result
        • 7.3.1 Physical apparatus
        • 7.3.2 The Hamiltonian
        • 7.3.3 Quantum computation
        • 7.3.4 Drawbacks
          • Harmonic oscillator quantum computer
      • ﾿
        • 7.4.1 Physical apparatus
        • 7.4.2 Quantum computation
        • 7.4.3 Drawbacks
          • Optical photon quantum computer
        • 7.5.1 Physical apparatus
          • FabryPerot cavity
          • Two-level atoms
        • 7.5.2 The Hamiltonian
        • 7.5.3 Single-photon single-atom absorption and refraction
        • 7.5.4 Quantum computation
          • Optical cavity quantum electrodynamics
        • 7.6.1 Physical apparatus
          • Trap geometry and lasers
          • Atomic structure
        • 7.6.2 The Hamiltonian
        • 7.6.3 Quantum computation
          • Single qubit operations
          • Controlled phase-flip gate
          • Swap gate
          • Controlled-NOT gate
          • Ion trap quantum computer
      • 7.7 Nuclear magnetic resonance
        • 7.7.1 Physical apparatus
        • 7.7.2 The Hamiltonian
          • Single spin dynamics
          • Spinspin couplings
          • Thermal equilibrium
          • Magnetization readout
          • Decoherence
        • 7.7.3 Quantum computation
          • Refocusing
          • Controlled-NOT gate
          • Temporal, spatial, and logical labeling
          • Ensemble readout of quantum algorithm results
        • 7.7.4 Experiment
          • State tomography
          • Quantum logic gates
          • Quantum algorithms
          • Drawbacks
      • 7.8 Other implementation schemes
      • History and further reading
  • III Quantum information
    • 8 Quantum noise and quantum operations
      • 8.1 Classical noise and Markov processes
      • 8.2 Quantum operations
        • 8.2.1 Overview
        • 8.2.2 Environments and quantum operations
        • 8.2.3 Operator-sum representation
          • Physical interpretation of the operator-sum representation
          • Measurements and the operator-sum representation
          • Systemenvironment models for any operator-sum representation
        • 8.2.4 Axiomatic approach to quantum operations
          • Freedom in the operator-sum representation
      • 8.3 Examples of quantum noise and quantum operations
        • 8.3.1 Trace and partial trace
        • 8.3.2 Geometric picture of single qubit quantum operations
        • 8.3.3 Bit flip and phase flip channels
        • 8.3.4 Depolarizing channel
        • 8.3.5 Amplitude damping
        • 8.3.6 Phase damping
      • 8.4 Applications of quantum operations
        • 8.4.1 Master equations
        • 8.4.2 Quantum process tomography
      • 8.5 Limitations of the quantum operations formalism
      • History and further reading
    • 9 Distance measures for quantum information
      • 9.1 Distance measures for classical information
      • 9.2 How close are two quantum states?
        • 9.2.1 Trace distance
        • 9.2.2 Fidelity
        • 9.2.3 Relationships between distance measures
      • 9.3 How well does a quantum channel preserve information?
        • Quantum sources of information and the entanglement fidelity
      • History and further reading
    • 10 Quantum error-correction
      • 10.1 Introduction
        • 10.1.1 The three qubit bit flip code
          • Improving the error analysis
        • 10.1.2 Three qubit phase flip code
      • 10.2 The Shor code
      • 10.3 Theory of quantum error-correction
        • 10.3.1 Discretization of the errors
        • 10.3.2 Independent error models
        • 10.3.3 Degenerate codes
        • 10.3.4 The quantum Hamming bound
      • 10.4 Constructing quantum codes
        • 10.4.1 Classical linear codes
        • 10.4.2 CalderbankŅShorSteane codes
          • The Steane code
      • 10.5 Stabilizer codes
        • 10.5.1 The stabilizer formalism
        • 10.5.2 Unitary gates and the stabilizer formalism
        • 10.5.3 Measurement in the stabilizer formalism
        • 10.5.4 The GottesmanŅKnill theorem
        • 10.5.5 Stabilizer code constructions
        • 10.5.6 Examples
          • The three qubit bit flip code
          • The nine qubit Shor code
          • The five qubit code
          • CSS codes and the seven qubit code
        • 10.5.7 Standard form for a stabilizer code
        • 10.5.8 Quantum circuits for encoding, decoding, and correction
      • 10.6 Fault-tolerant quantum computation
        • 10.6.1 Fault-tolerance: the big picture
          • Fundamental issues
          • Fault-tolerant operations: definitions
          • Example: fault-tolerant controlled-NOT
          • Concatenated codes and the threshold theorem
        • 10.6.2 Fault-tolerant quantum logic
          • Normalizer operations
        • 10.6.3 Fault-tolerant measurement
          • Measurement of stabilizer generators
        • 10.6.4 Elements of resilient quantum computation
      • History and further reading
    • 11 Entropy and information
      • 11.1 Shannon entropy
      • 11.2 Basic properties of entropy
        • 11.2.1 The binary entropy
        • 11.2.2 The relative entropy
        • 11.2.3 Conditional entropy and mutual information
        • 11.2.4 The data processing inequality
      • 11.3 Von Neumann entropy
        • 11.3.1 Quantum relative entropy
        • 11.3.2 Basic properties of entropy
        • 11.3.3 Measurements and entropy
        • 11.3.4 Subadditivity
        • 11.3.5 Concavity of the entropy
        • 11.3.6 The entropy of a mixture of quantum states
      • 11.4 Strong subadditivity
        • 11.4.1 Proof of strong subadditivity
        • 11.4.2 Strong subadditivity: elementary applications
      • History and further reading
      • 12.1 Distinguishing quantum states and the accessible information
        • 12.1.1 The Holevo bound
      • 12.2 Data compression
        • 12.2.1 Shannons noiseless channel coding theorem
        • 12.2.2 Schumachers quantum noiseless channel coding theorem
      • 12.3 Classical information over noisy quantum channels
        • 12.3.1 Communication over noisy classical channels
          • Random coding for the binary symmetric channel
          • Shannons noisy channel coding theorem
        • 12.3.2 Communication over noisy quantum channels
          • Random coding
          • Proof of the upper bound
          • Examples
      • 12.4 Quantum information over noisy quantum channels
        • 12.4.1 Entropy exchange and the quantum Fano inequality
        • 12.4.2 The quantum data processing inequality
        • 12.4.3 Quantum Singleton bound
        • 12.4.4 Quantum error-correction, refrigeration and MaxwellАs demon
      • 12.5 Entanglement as a physical resource
        • 12.5.1 Transforming bi-partite pure state entanglement
        • 12.5.2 Entanglement distillation and dilution
        • 12.5.3 Entanglement distillation and quantum error-correction
        • 12.6.1 Private key cryptography
        • 12.6.2 Privacy amplification and information reconciliation
          • CSS code privacy amplification & information reconciliation
        • 12.6.3 Quantum key distribution
          • The BB84 protocol
          • The B92 protocol
        • 12.6.4 Privacy and coherent information
        • 12.6.5 The security of quantum key distribution
          • Requirements for a secure QKD protocol
          • Random sampling can upper-bound eavesdropping
          • The modified LoChau protocol
          • A quantum error-correction protocol
          • Reduction to BB84
      • History and further reading
  • ﾿
    • A2.1 Basic definitions
      • A2.1.1 Generators
      • A2.1.2 Cyclic groups
      • A2.1.3 Cosets
      • A2.2.1 Equivalence and reducibility
      • A2.2.2 Orthogonality
      • A2.2.3 The regular representation
    • ﾿
  • ﾿
    • A4.3 Reduction of factoring to order-finding
    • ﾿
  • Appendix 5: Public key cryptography and the RSA cryptosystem
  • ﾿
  • Bibliography
  • Index