Quantum Computation and Quantum InformationIn this first comprehensive introduction to the main ideas and techniques of quantum computation and information, Michael Nielsen and Isaac Chuang ask the question: What are the ultimate physical limits to computation and communication? They detail such remarkable effects as fast quantum algorithms, quantum teleportation, quantum cryptography and quantum error correction. A wealth of accompanying figures and exercises illustrate and develop the material in more depth. They describe what a quantum computer is, how it can be used to solve problems faster than familiar "classical" computers, and the real-world implementation of quantum computers. Their book concludes with an explanation of how quantum states can be used to perform remarkable feats of communication, and of how it is possible to protect quantum states against the effects of noise. |
Contents
Fundamental concepts | 1 |
111 History of quantum computation and quantum information | 2 |
112 Future directions | 12 |
12 Quantum bits | 13 |
121 Multiple qubits | 16 |
13 Quantum computation | 17 |
132 Multiple qubit gates | 20 |
133 Measurements in bases other than the computational basis | 22 |
754 Quantum computation | 306 |
76 Ion traps | 309 |
762 The Hamiltonian | 317 |
763 Quantum computation | 319 |
764 Experiment | 321 |
77 Nuclear magnetic resonance | 324 |
771 Physical apparatus | 325 |
772 The Hamiltonian | 326 |
135 Qubit copying circuit? | 24 |
Bell states | 25 |
quantum teleportation | 26 |
14 Quantum algorithms | 28 |
141 Classical computations on a quantum computer | 29 |
142 Quantum parallelism | 30 |
143 Deutschs algorithm | 32 |
144 The DeutschJozsa algorithm | 34 |
145 Quantum algorithms summarized | 36 |
15 Experimental quantum information processing | 42 |
151 The SternGerlach experiment | 43 |
152 Prospects for practical quantum information processing | 46 |
16 Quantum information | 50 |
example problems | 52 |
162 Quantum information in a wider context | 58 |
Introduction to quantum mechanics | 60 |
21 Linear algebra | 61 |
211 Bases and linear independence | 62 |
212 Linear operators and matrices | 63 |
213 The Pauli matrices | 65 |
215 Eigenvectors and eigenvalues | 68 |
216 Adjoints and Hermitian operators | 69 |
217 Tensor products | 71 |
218 Operator functions | 75 |
219 The commutator and anticommutator | 76 |
2110 The polar and singular value decompositions | 78 |
22 The postulates of quantum mechanics | 80 |
222 Evolution | 81 |
223 Quantum measurement | 84 |
224 Distinguishing quantum states | 86 |
225 Projective measurements | 87 |
226 POVM measurements | 90 |
227 Phase | 93 |
a global view | 96 |
superdense coding | 97 |
24 The density operator | 98 |
241 Ensembles of quantum states | 99 |
242 General properties of the density operator | 101 |
243 The reduced density operator | 105 |
25 The Schmidt decomposition and purifications | 109 |
26 EPR and the Bell inequality | 111 |
Introduction to computer science | 120 |
31 Models for computation | 122 |
312 Circuits | 129 |
32 The analysis of computational problems | 135 |
321 How to quantify computational resources | 136 |
322 Computational complexity | 138 |
323 Decision problems and the complexity classes P and NP | 141 |
324 A plethora of complexity classes | 150 |
325 Energy and computation | 153 |
33 Perspectives on computer science | 161 |
Quantum computation | 171 |
41 Quantum algorithms | 172 |
42 Single qubit operations | 174 |
43 Controlled operations | 177 |
44 Measurement | 185 |
45 Universal quantum gates | 188 |
451 Twolevel unitary gates are universal | 189 |
452 Single qubit and CNOT gates are universal | 191 |
453 A discrete set of universal operations | 194 |
454 Approximating arbitrary unitary gates is generically hard | 198 |
455 Quantum computational complexity | 200 |
46 Summary of the quantum circuit model of computation | 202 |
47 Simulation of quantum systems | 204 |
472 The quantum simulation algorithm | 206 |
473 An illustrative example | 209 |
474 Perspectives on quantum simulation | 211 |
The quantum Fourier transform and its applications | 216 |
51 The quantum Fourier transform | 217 |
52 Phase estimation | 221 |
521 Performance and requirements | 223 |
orderfinding and factoring | 226 |
factoring | 232 |
54 General applications of the quantum Fourier transform | 234 |
541 Periodfinding | 236 |
542 Discrete logarithms | 238 |
543 The hidden subgroup problem | 240 |
544 Other quantum algorithms? | 242 |
Quantum search algorithms | 248 |
612 The procedure | 250 |
613 Geometric visualization | 252 |
614 Performance | 253 |
62 Quantum search as a quantum simulation | 255 |
63 Quantum counting | 261 |
64 Speeding up the solution of NPcomplete problems | 263 |
65 Quantum search of an unstructured database | 265 |
66 Optimality of the search algorithm | 269 |
67 Black box algorithm limits | 271 |
Quantum computers physical realization | 277 |
72 Conditions for quantum computation | 279 |
722 Performance of unitary transformations | 281 |
724 Measurement of output result | 282 |
73 Harmonic oscillator quantum computer | 283 |
732 The Hamiltonian | 284 |
733 Quantum computation | 286 |
74 Optical photon quantum computer | 287 |
742 Quantum computation | 290 |
743 Drawbacks | 296 |
75 Optical cavity quantum electrodynamics | 297 |
751 Physical apparatus | 298 |
752 The Hamiltonian | 300 |
753 Singlephoton singleatom absorption and refraction | 303 |
773 Quantum computation | 331 |
774 Experiment | 336 |
78 Other implementation schemes | 343 |
Quantum information | 353 |
81 Classical noise and Markov processes | 354 |
82 Quantum operations | 356 |
822 Environments and quantum operations | 357 |
823 Operatorsum representation | 360 |
824 Axiomatic approach to quantum operations | 366 |
83 Examples of quantum noise and quantum operations | 373 |
831 Trace and partial trace | 374 |
833 Bit flip and phase flip channels | 376 |
834 Depolarizing channel | 378 |
835 Amplitude damping | 380 |
836 Phase damping | 383 |
84 Applications of quantum operations | 386 |
842 Quantum process tomography | 389 |
85 Limitations of the quantum operations formalism | 394 |
Distance measures for quantum information | 399 |
92 How close are two quantum states? | 403 |
922 Fidelity | 409 |
923 Relationships between distance measures | 415 |
93 How well does a quantum channel preserve information? | 416 |
Quantum errorcorrection | 425 |
101 Introduction | 426 |
1011 The three qubit bit flip code | 427 |
1012 Three qubit phase flip code | 430 |
102 The Shor code | 432 |
103 Theory of quantum errorcorrection | 435 |
1031 Diseretization of the errors | 438 |
1032 Independent error models | 441 |
1033 Degenerate codes | 444 |
104 Constructing quantum codes | 445 |
1042 CalderbankShorSteane codes | 450 |
105 Stabilizer codes | 453 |
1051 The stabilizer formalism | 454 |
1052 Unitary gates and the stabilizer formalism | 459 |
1053 Measurement in the stabilizer formalism | 463 |
1054 The GottesmanKnill theorem | 464 |
1056 Examples | 467 |
1057 Standard form for a stabilizer code | 470 |
1058 Quantum circuits for encoding decoding and correction | 472 |
106 Faulttolerant quantum computation | 474 |
the big picture | 475 |
1062 Faulttolerant quantum logic | 482 |
1063 Faulttolerant measurement | 489 |
1064 Elements of resilient quantum computation | 493 |
Entropy and information | 500 |
112 Basic properties of entropy | 502 |
1122 The relative entropy | 504 |
1123 Conditional entropy and mutual information | 505 |
1124 The data processing inequality | 509 |
113 Von Neumann entropy | 510 |
1131 Quantum relative entropy | 511 |
1132 Basic properties of entropy | 513 |
1133 Measurements and entropy | 514 |
1134 Subadditivity | 515 |
1135 Concavity of the entropy | 516 |
1136 The entropy of a mixture of quantum states | 518 |
114 Strong subadditivity | 519 |
elementary applications | 522 |
Quantum information theory | 528 |
121 Distinguishing quantum states and the accessible information | 529 |
1211 The Holevo bound | 531 |
1212 Example applications of the Holevo bound | 534 |
122 Data compression | 536 |
1221 Shannons noiseless channel coding theorem | 537 |
1222 Schumachers quantum noiseless channel coding theorem | 542 |
123 Classical information over noisy quantum channels | 546 |
1231 Communication over noisy classical channels | 548 |
1232 Communication over noisy quantum channels | 554 |
124 Quantum information over noisy quantum channels | 561 |
1242 The quantum data processing inequality | 564 |
1243 Quantum Singleton bound | 568 |
1244 Quantum errorcorrection refrigeration and Maxwells demon | 569 |
125 Entanglement as a physical resource | 571 |
1251 Transforming bipartite pure state entanglement | 573 |
1252 Entanglement distillation and dilution | 578 |
1253 Entanglement distillation and quantum errorcorrection | 580 |
126 Quantum cryptography | 582 |
1262 Privacy amplification and information reconciliation | 584 |
1263 Quantum key distribution | 586 |
1264 Privacy and coherent information | 592 |
1265 The security of quantum key distribution | 593 |
Notes on basic probability theory | 608 |
Group theory | 610 |
A211 Generators | 611 |
A213 Cosets | 612 |
A222 Orthogonality | 613 |
A223 The regular representation | 614 |
A23 Fourier transforms | 615 |
The SolovayKitaev theorem | 617 |
Number theory | 625 |
A42 Modular arithmetic and Euclids algorithm | 626 |
A43 Reduction of factoring to orderfinding | 633 |
A44 Continued fractions | 635 |
Public key cryptography and the RSA cryptosystem | 640 |
Proof of Liebs theorem | 645 |
649 | |
665 | |
Other editions - View all
Quantum Computation and Quantum Information Michael A. Nielsen,Isaac L. Chuang No preview available - 2000 |
Quantum Computation and Quantum Information Michael A. Nielsen,Isaac L. Chuang No preview available - 2000 |
Common terms and phrases
Alice and Bob ancilla applied arbitrary atom bit flip Bloch sphere C₁ chapter classical computer classical information CNOT computation and quantum computational basis construction controlled-NOT gate defined density matrix density operator described efficiently eigenstates eigenvalues encoded entanglement entropy equation error error-correcting codes example Exercise factor fault-tolerant fidelity Figure finite function gives Hadamard gate Hamiltonian implemented inequality input integer interaction known linear model of computation noise notation obtain operation elements oracle order-finding output Pauli perform phase estimation phase flip physical polynomial possible POVM probability problem procedure proof properties protocol prove quantum algorithms quantum circuit quantum codes quantum computation quantum error-correction quantum Fourier transform quantum information processing quantum information theory quantum mechanics quantum operation quantum search algorithm quantum system result Section Show simulation single qubit solve spin subadditivity Suppose Toffoli gate trace distance Turing machine unitary matrix unitary operator unitary transform vector space
References to this book
Classical and Quantum Computation Alexei Yu. Kitaev,Alexander Shen,Mikhail N. Vyalyi No preview available - 2002 |