Quantum Computation and Quantum Information
10th Anniversary Edition
. Nielsen & . AMBRIDGE UNIVERSITY PRESS
Cambridge, , Melbourne, Madrid, Cape Town, Singapore, Sa ̃o Paulo, Delhi, Dubai, Tokyo, Mexico City
Copyright By PowCoder代写 加微信 powcoder
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press,
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 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
Introduction to the Tenth Anniversary Edition Afterword to the Tenth Anniversary Edition Preface
Acknowledgements
Nomenclature and notation
Part I Fundamental concepts
1 Introduction and overview
1.1 Global perspectives
1.1.1 History of quantum computation and quantum
information
1.1.2 Future directions
1.2 Quantum bits
1.2.1 Multiple qubits
1.3 Quantum computation
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 Quantum algorithms
1.4.1 Classical computations on a quantum computer 1.4.2 Quantum parallelism
1.4.3 Deutsch’s algorithm
1.4.4 The Deutsch–Jozsa algorithm
1.4.5 Quantum algorithms summarized
1.5 Experimental quantum information processing
1.5.1 The Stern–Gerlach experiment
1.5.2 Prospects for practical quantum information processing
1.6 Quantum information
1.6.1 Quantum information theory: example problems 1.6.2 Quantum information in a wider context
page xvii xix xxi xxvii xxix
2 Introduction to quantum mechanics 60
2.1 Linear algebra 61 2.1.1 Bases and linear independence 62 2.1.2 Linear operators and matrices 63 2.1.3 The Pauli matrices 65 2.1.4 Inner products 65 2.1.5 Eigenvectors and eigenvalues 68 2.1.6 Adjoints and Hermitian operators 69 2.1.7 Tensor products 71 2.1.8 Operator functions 75 2.1.9 The commutator and anti-commutator 76 2.1.10 The polar and singular value decompositions 78
2.2 The postulates of quantum mechanics 80 2.2.1 State space 80 2.2.2 Evolution 81 2.2.3 Quantum measurement 84 2.2.4 Distinguishing quantum states 86 2.2.5 Projective measurements 87 2.2.6 POVM measurements 90 2.2.7 Phase 93 2.2.8 Composite systems 93 2.2.9 Quantum mechanics: a global view 96
2.3 Application: superdense coding 97
2.4 The density operator 98 2.4.1 Ensembles of quantum states 99 2.4.2 General properties of the density operator 101 2.4.3 The reduced density operator 105
2.5 The Schmidt decomposition and purifications 109
2.6 EPR and the Bell inequality 111
3 Introduction to computer science 120 3.1 Models for computation 122 3.1.1 Turing machines 122 3.1.2 Circuits 129 3.2 The analysis of computational problems 135 3.2.1 How to quantify computational resources 136 3.2.2 Computational complexity 138 3.2.3 Decision problems and the complexity classes P and NP 141 3.2.4 A plethora of complexity classes 150 3.2.5 Energy and computation 153 3.3 Perspectives on computer science 161
Part II Quantum computation 171
4 Quantum circuits 171 4.1 Quantum algorithms 172 4.2 Single qubit operations 174
Contents xi
4.3 Controlled operations 177 4.4 Measurement 185 4.5 Universal quantum gates 188
4.5.1 Two-level unitary gates are universal 189 4.5.2 Single qubit and CNOT gates are universal 191 4.5.3 A discrete set of universal operations 194 4.5.4 Approximating arbitrary unitary gates is generically hard 198 4.5.5 Quantum computational complexity 200
4.6 Summary of the quantum circuit model of computation 202 4.7 Simulation of quantum systems 204 4.7.1 Simulation in action 204 4.7.2 The quantum simulation algorithm 206 4.7.3 An illustrative example 209 4.7.4 Perspectives on quantum simulation 211
5 The quantum Fourier transform and its applications 216 5.1 The quantum Fourier transform 217 5.2 Phase estimation 221
5.2.1 Performance and requirements 223 5.3 Applications: order-finding and factoring 226 5.3.1 Application: order-finding 226 5.3.2 Application: factoring 232
5.4 General applications of the quantum Fourier
transform 234
5.4.1 Period-finding 236 5.4.2 Discrete logarithms 238 5.4.3 The hidden subgroup problem 240 5.4.4 Other quantum algorithms? 242
6 Quantum search algorithms 248 6.1 The quantum search algorithm 248 6.1.1 The oracle 248 6.1.2 The procedure 250 6.1.3 Geometric visualization 252 6.1.4 Performance 253 6.2 Quantum search as a quantum simulation 255 6.3 Quantum counting 261 6.4 Speeding up the solution of NP-complete problems 263 6.5 Quantum search of an unstructured database 265 6.6 Optimality of the search algorithm 269 6.7 Black box algorithm limits 271
7 Quantum computers: physical realization 277 7.1 Guiding principles 277 7.2 Conditions for quantum computation 279
7.2.1 Representation of quantum information 279 7.2.2 Performance of unitary transformations 281
7.2.3 Preparation of fiducial initial states 281
7.2.4 Measurement of output result 282 7.3 Harmonic oscillator quantum computer 283 7.3.1 Physical apparatus 283 7.3.2 The Hamiltonian 284 7.3.3 Quantum computation 286 7.3.4 Drawbacks 286 7.4 Optical photon quantum computer 287 7.4.1 Physical apparatus 287 7.4.2 Quantum computation 290 7.4.3 Drawbacks 296 7.5 Optical cavity quantum electrodynamics 297
7.5.1 Physical apparatus 298
7.5.2 The Hamiltonian 300
7.5.3 Single-photon single-atom absorption and
refraction 303
7.5.4 Quantum computation 306
7.6 Ion traps 309 7.6.1 Physical apparatus 309 7.6.2 The Hamiltonian 317 7.6.3 Quantum computation 319 7.6.4 Experiment 321 7.7 Nuclear magnetic resonance 324 7.7.1 Physical apparatus 325 7.7.2 The Hamiltonian 326 7.7.3 Quantum computation 331 7.7.4 Experiment 336 7.8 Other implementation schemes 343
Part III Quantum information 353
8 Quantum noise and quantum operations 353 8.1 Classical noise and Markov processes 354 8.2 Quantum operations 356
8.2.1 Overview 356 8.2.2 Environments and quantum operations 357 8.2.3 Operator-sum representation 360 8.2.4 Axiomatic approach to quantum operations 366
8.3 Examples of quantum noise and quantum operations 373
8.3.1 Trace and partial trace 374
8.3.2 Geometric picture of single qubit quantum
operations 374
8.3.3 Bit flip and phase flip channels 376
8.3.4 Depolarizing channel 378
8.3.5 Amplitude damping 380
8.3.6 Phase damping 383
Contents xiii
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
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?
10 Quantum error-correction
10.1 Introduction
10.1.1 The three qubit bit flip code 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–Shor–Steane codes
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
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
10.6.2 Fault-tolerant quantum logic
10.6.3 Fault-tolerant measurement
10.6.4 Elements of resilient quantum computation
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 505 11.2.4 The data processing inequality 509 entropy 510 11.3.1 Quantum relative entropy 511 11.3.2 Basic properties of entropy 513 11.3.3 Measurements and entropy 514 11.3.4 Subadditivity 515 11.3.5 Concavity of the entropy 516 11.3.6 The entropy of a mixture of quantum states 518 Strong subadditivity 519 11.4.1 Proof of strong subadditivity 519 11.4.2 Strong subadditivity: elementary applications 522
12 Quantum information theory 528
12.1 Distinguishing quantum states and the accessible information 529 12.1.1 The Holevo bound 531 12.1.2 Example applications of the Holevo bound 534
12.2 Data compression 536 12.2.1 Shannon’s noiseless channel coding theorem 537 12.2.2 Schumacher’s quantum noiseless channel coding theorem 542
12.3 Classical information over noisy quantum channels 546 12.3.1 Communication over noisy classical channels 548 12.3.2 Communication over noisy quantum channels 554
12.4 Quantum information over noisy quantum channels 561 12.4.1 Entropy exchange and the quantum Fano inequality 561 12.4.2 The quantum data processing inequality 564 12.4.3 Quantum Singleton bound 568 12.4.4 Quantum error-correction, refrigeration and Maxwell’s demon 569
12.5 Entanglement as a physical resource 571 12.5.1 Transforming bi-partite pure state entanglement 573 12.5.2 Entanglement distillation and dilution 578 12.5.3 Entanglement distillation and quantum error-correction 580
12.6 Quantum cryptography 582 12.6.1 Private key cryptography 582 12.6.2 Privacy amplification and information reconciliation 584 12.6.3 Quantum key distribution 586 12.6.4 Privacy and coherent information 592 12.6.5 The security of quantum key distribution 593
Appendices Appendix 1:
608 Notes on basic probability theory 608
Group theory 610 A2.1 Basic definitions 610 A2.1.1 Generators 611 A2.1.2 Cyclic groups 611 A2.1.3 Cosets 612
Appendix 2:
A2.2 Representations 612 A2.2.1 Equivalence and reducibility 612 A2.2.2 Orthogonality 613 A2.2.3 The regular representation 614
A2.3 Fourier transforms 615
Appendix 3: The Solovay–Kitaev theorem 617
Appendix 4: Number theory 625 A4.1 Fundamentals 625 A4.2 Modular arithmetic and Euclid’s algorithm 626 A4.3 Reduction of factoring to order-finding 633 A4.4 Continued fractions 635
Appendix 5:
Appendix 6: Bibliography
Public key cryptography and the RSA cryptosystem 640 Proof of Lieb’s theorem 645 649 665
Contents xv
Introduction to the Tenth Anniversary Edition
Quantum mechanics has the curious distinction of being simultaneously the most suc- cessful and the most mysterious of our scientific theories. It was developed in fits and starts over a remarkable period from 1900 to the 1920s, maturing into its current form in the late 1920s. In the decades following the 1920s, physicists had great success applying quantum mechanics to understand the fundamental particles and forces of nature, cul- minating in the development of the standard model of particle physics. Over the same period, physicists had equally great success in applying quantum mechanics to understand an astonishing range of phenomena in our world, from polymers to semiconductors, from superfluids to superconductors. But, while these developments profoundly advanced our understanding of the natural world, they did only a little to improve our understanding of quantum mechanics.
This began to change in the 1970s and 1980s, when a few pioneers were inspired to ask whether some of the fundamental questions of computer science and information theory could be applied to the study of quantum systems. Instead of looking at quantum systems purely as phenomena to be explained as they are found in nature, they looked at them as systems that can be designed. This seems a small change in perspective, but the implications are profound. No longer is the quantum world taken merely as presented, but instead it can be created. The result was a new perspective that inspired both a resurgence of interest in the fundamentals of quantum mechanics, and also many new questions combining physics, computer science, and information theory. These include questions such as: what are the fundamental physical limitations on the space and time required to construct a quantum state? How much time and space are required for a given dynamical operation? What makes quantum systems difficult to understand and simulate by conventional classical means?
Writing this book in the late 1990s, we were fortunate to be writing at a time when these and other fundamental questions had just crystallized out. Ten years later it is clear such questions offer a sustained force encouraging a broad research program at the foundations of physics and computer science. Quantum information science is here to stay. Although the theoretical foundations of the field remain similar to what we discussed 10 years ago, detailed knowledge in many areas has greatly progressed. Originally, this book served as a comprehensive overview of the field, bringing readers near to the forefront of research. Today, the book provides a basic foundation for understanding the field, appropriate either for someone who desires a broad perspective on quantum information science, or an entryway for further investigation of the latest research literature. Of course,
xviii Introduction to the Tenth Anniversary Edition
many fundamental challenges remain, and meeting those challenges promises to stimulate exciting and unexpected links among many disparate parts of physics, computer science, and information theory. We look forward to the decades ahead!
– . Nielsen and . Chuang, March, 2010.
Afterword to the Tenth Anniversary Edition
An enormous amount has happened in quantum information science in the 10 years since the first edition of this book, and in this afterword we cannot summarize even a tiny fraction of that work. But a few especially striking developments merit comment, and may perhaps whet your appetite for more.
Perhaps the most impressive progress has been in the area of experimental implemen- tation. While we are still many years from building large-scale quantum computers, much progress has been made. Superconducting circuits have been used to implement simple two-qubit quantum algorithms, and three-qubit systems are nearly within reach. Qubits based on nuclear spins and single photons have been used, respectively, to demonstrate proof-of-principle for simple forms of quantum error correction and quantum simulation. But the most impressive progress of all has been made with trapped ion systems, which have been used to implement many two- and three-qubit algorithms and algorithmic building blocks, including the quantum search algorithm and the quantum Fourier trans- form. Trapped ions have also been used to demonstrate basic quantum communication primitives, including quantum error correction and quantum teleportation.
A second area of progress has been in understanding what physical resources are required to quantum compute. Perhaps the most intriguing breakthrough here has been the discovery that quantum computation can be done via measurement alone. For many years, the conventional wisdom was that coherent superposition-preserving unitary dynamics was an essential part of the power of quantum computers. This conventional wisdom was blown away by the realization that quantum computation can be done without any unitary dynamics at all. Instead, in some new models of quantum computation, quantum measurements alone can be used to do arbitrary quantum computations. The only coherent resource in these models is quantum memory, i.e., the ability to store quantum information. An especially interesting example of these models is the one-way quantum computer, or cluster-state computer. To quantum compute in the cluster-state model requires only that the experimenter have possession of a fixed universal state known as the cluster state. With a cluster state in hand, quantum computation can be implemented simply by doing a sequence of single-qubit measurements, with the particular computation done being determined by which qubits are measured, when they are measured, and how they are measured. This is remarkable: you’re given a fixed quantum state, and then quantum compute by “looking” at the individual qubits in appropriate ways.
A third area of progress has been in classically simulating quantum systems. Feynman’s pioneering 1982 paper on quantum computing was motivated in part by the observation that quantum systems often seem hard to simulate on conventional classical computers. Of course, at the time there was only a limited understanding of how difficult it is to simulate different quantum systems on ordinary classical computers. But in the 1990s and, especially, in the 2000s, we have learned much about which quantum systems are easy
xx Afterword to the Tenth Anniversary Edition
to simulate, and which are hard. Ingenious algorithms have been developed to classically simulate many quantum systems that were formerly thought to be hard to simulate, in particular, many quantum systems in one spatial dimension, and certain two-dimensional quantum systems. These classical algorithms have been made possible by the development of insightful classical descriptions that capture in a compact way much or all of the essential physics of the system in question. At the same time, we have learned that some systems that formerly seemed simple are surprisingly complex. For example, it has long been known that quantum systems based on a certain type of optical component – what are called linear optical systems – are easily simulated classically. So it was surprising when it was discovered that adding two seemingly innocuous components – single-photon sources and photodetectors – gave linear optics the full power of quantum computation. These and similar investigations have deepened our understanding of which quantum systems are easy to simulate, which quantum systems are hard to simulate, and why.
A fourth area of progress has been a greatly deepened understanding of quantum communication channels. A beautiful and complete theory has been developed of how entangled quantum states can assist classical communication over quantum channels. A plethora of different quantum protocols for communication have been organized into a comprehensive family (headed by “mother” and “father” protocols), unifying much of our understanding of the different types of communication possible with quantum information. A sign of the progress is the disproof of one of the key unsolved conjectures reported in this book (p. 554), namely, that the communication capacity of a quantum channel with product states is equal to the unconstrained capacity (i.e., the capacity with any entangled state allowed as input). But, despite the progress, much remains beyond our understanding. Only ve
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com