Quantum_Computation and Quantum Information
Textonly 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
Information 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
errorcorrection. 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 realworld implementation. It concludes with
an indepth treatment of quantum information.
Containing a wealth of figures and exercises, this wellknown 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
Toronto.
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
molecules.
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
ChurchTuring Thesis to the nittygritty of bra/ket manipulation. A dogeared 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 wellperused 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 stillyoung 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
mathematicallyimpaired 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
discussion.
Michael Freedman, Fields Medalist, Microsoft
Nielsen and Chuang's new text is remarkably thorough and uptodate, 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 selfcontained 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
well.
Peter Shor, Massachusetts Institute of Technology
Quantum Computation and Quantum Information
10th Anniversary Edition
Michael A. Nielsen & Isaac L. Chuang
C A M B R I D G E U N I V E R S I T Y P R E S S
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
www.cambridge.org
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 9781107002173 Hardback
Cambridge University Press has no responsibility for the persistence or
accuracy of URLs for external or thirdparty 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
 Halftitle
 Seriestitle
 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 Deutschs 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
 1.6.1 Quantum information theory: example problems


 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 anticommutator
 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


 2.1 Linear algebra

 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
 3.2.1 How to quantify computational resources







 4.5.1 Twolevel 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: orderfinding and factoring
 5.3.1 Application: orderfinding
 The continued fraction expansion
 Performance
 5.3.2 Application: factoring
 5.3.1 Application: orderfinding

 5.4.1 Periodfinding
 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 NPcomplete 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
 FabryPerot cavity
 Twolevel atoms
 7.5.2 The Hamiltonian
 7.5.3 Singlephoton singleatom absorption and refraction
 7.5.4 Quantum computation
 Optical cavity quantum electrodynamics
 7.5.1 Physical apparatus
 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 phaseflip gate
 Swap gate
 ControlledNOT gate
 Ion trap quantum computer
 7.6.1 Physical apparatus
 7.7 Nuclear magnetic resonance
 7.7.1 Physical apparatus
 7.7.2 The Hamiltonian
 Single spin dynamics
 Spinspin couplings
 Thermal equilibrium
 Magnetization readout
 Decoherence
 7.7.3 Quantum computation
 Refocusing
 ControlledNOT 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 Operatorsum representation
 Physical interpretation of the operatorsum representation
 Measurements and the operatorsum representation
 Systemenvironment models for any operatorsum representation
 8.2.4 Axiomatic approach to quantum operations
 Freedom in the operatorsum 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 errorcorrection
 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.1.1 The three qubit bit flip code
 10.2 The Shor code
 10.3 Theory of quantum errorcorrection
 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 Faulttolerant quantum computation
 10.6.1 Faulttolerance: the big picture
 Fundamental issues
 Faulttolerant operations: definitions
 Example: faulttolerant controlledNOT
 Concatenated codes and the threshold theorem
 10.6.2 Faulttolerant quantum logic
 Normalizer operations
 10.6.3 Faulttolerant measurement
 Measurement of stabilizer generators
 10.6.4 Elements of resilient quantum computation
 10.6.1 Faulttolerance: the big picture
 History and further reading
 10.1 Introduction
 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 Schumachers 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.3.1 Communication over noisy classical channels
 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 errorcorrection, refrigeration and MaxwellАs demon
 12.5 Entanglement as a physical resource
 12.5.1 Transforming bipartite pure state entanglement
 12.5.2 Entanglement distillation and dilution
 12.5.3 Entanglement distillation and quantum errorcorrection
 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 upperbound eavesdropping
 The modified LoChau protocol
 A quantum errorcorrection protocol
 Reduction to BB84
 History and further reading
 12.1 Distinguishing quantum states and the accessible information
 8 Quantum noise and quantum operations


 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


 A2.1 Basic definitions



 A4.3 Reduction of factoring to orderfinding

 Appendix 5: Public key cryptography and the RSA cryptosystem


 Bibliography
 Index