Contents xin 8.4 Applications of quantum operations 386 8.4.1 Master equations 386 8.4.2 Quantum process tomography 389 8.5 Limitations of the quantum operations formalism 394 9 Distance measures for quantum information 399 9.1 Distance measures for classical information 399 9.2 How close are two quantum states? 403 9.2.1 Trace distance 403 9.2.2 Fidelity 409 9.2.3 Relationships between distance measures 415 9.3 How well does a quantum channel preserve information? 416 10 Quantum error-correction 425 10.1 Introduction 426 10.1.1 The three qubit bit flip code 427 10.1.2 Three qubit phase flip code 430 10.2 The Shor code 432 10.3 Theory of quantum error-correction 435 10.3.1 Discretization of the errors 438 10.3.2 Independent error models 441 10.3.3 Degenerate codes 444 10.3.4 The quantum Hamming bound 444 10.4 Constructing quantum codes 445 10.4.1 Classical linear codes 445 10.4.2 Calderbank-Shor-Steane codes 450 10.5 Stabilizer codes 453 10.5.1 The stabilizer formalism 454 10.5.2 Unitary gates and the stabilizer formalism 459 10.5.3 Measurement in the stabilizer formalism 463 10.5.4 The Gottesman-Knill theorem 464 10.5.5 Stabilizer code constructions 464 10.5.6 Examples 467 10.5.7 Standard form for a stabilizer code 470 10.5.8 Quantum circuits for encoding,decoding,and correction 472 10.6 Fault-tolerant quantum computation 474 10.6.1 Fault-tolerance:the big picture 475 10.6.2 Fault-tolerant quantum logic 482 10.6.3 Fault-tolerant measurement 489 10.6.4 Elements of resilient quantum computation 493 11 Entropy and information 500 11.1 Shannon entropy 500 11.2 Basic properties of entropy 502 11.2.1 The binary entropy 502 11.2.2 The relative entropy 504
Contents xiii 8.4 Applications of quantum operations 386 8.4.1 Master equations 386 8.4.2 Quantum process tomography 389 8.5 Limitations of the quantum operations formalism 394 9 Distance measures for quantum information 399 9.1 Distance measures for classical information 399 9.2 How close are two quantum states? 403 9.2.1 Trace distance 403 9.2.2 Fidelity 409 9.2.3 Relationships between distance measures 415 9.3 How well does a quantum channel preserve information? 416 10 Quantum error-correction 425 10.1 Introduction 426 10.1.1 The three qubit bit flip code 427 10.1.2 Three qubit phase flip code 430 10.2 The Shor code 432 10.3 Theory of quantum error-correction 435 10.3.1 Discretization of the errors 438 10.3.2 Independent error models 441 10.3.3 Degenerate codes 444 10.3.4 The quantum Hamming bound 444 10.4 Constructing quantum codes 445 10.4.1 Classical linear codes 445 10.4.2 Calderbank–Shor–Steane codes 450 10.5 Stabilizer codes 453 10.5.1 The stabilizer formalism 454 10.5.2 Unitary gates and the stabilizer formalism 459 10.5.3 Measurement in the stabilizer formalism 463 10.5.4 The Gottesman–Knill theorem 464 10.5.5 Stabilizer code constructions 464 10.5.6 Examples 467 10.5.7 Standard form for a stabilizer code 470 10.5.8 Quantum circuits for encoding, decoding, and correction 472 10.6 Fault-tolerant quantum computation 474 10.6.1 Fault-tolerance: the big picture 475 10.6.2 Fault-tolerant quantum logic 482 10.6.3 Fault-tolerant measurement 489 10.6.4 Elements of resilient quantum computation 493 11 Entropy and information 500 11.1 Shannon entropy 500 11.2 Basic properties of entropy 502 11.2.1 The binary entropy 502 11.2.2 The relative entropy 504
xiv Contents 11.2.3 Conditional entropy and mutual information 505 11.2.4 The data processing inequality 509 11.3 Von Neumann 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 11.4 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 608 Appendix 1:Notes on basic probability theory 608 Appendix 2:Group theory 610 A2.1 Basic definitions 610 A2.1.1 Generators 611 A2.1.2 Cyclic groups 611 A2.1.3 Cosets 612
xiv Contents 11.2.3 Conditional entropy and mutual information 505 11.2.4 The data processing inequality 509 11.3 Von Neumann 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 11.4 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 608 Appendix 1: Notes on basic probability theory 608 Appendix 2: Group theory 610 A2.1 Basic definitions 610 A2.1.1 Generators 611 A2.1.2 Cyclic groups 611 A2.1.3 Cosets 612
Contents XV 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:Public key cryptography and the RSA cryptosystem 640 Appendix 6:Proof of Lieb's theorem 645 Bibliography 649 Index 665
Contents xv 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: Public key cryptography and the RSA cryptosystem 640 Appendix 6: Proof of Lieb’s theorem 645 Bibliography 649 Index 665
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 10yearsago,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.Ofcourse
Introduction to the Tenth Anniversary Edition Quantum mechanics has the curious distinction of being simultaneously the most successful 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, culminating 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! -Michael A.Nielsen and Isaac L.Chuang,March,2010
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! – Michael A. Nielsen and Isaac L. Chuang, March, 2010