Quantum computation and quantum information

Cover......Page 1
Half-title......Page 3
Series-title......Page 4
Title......Page 7
Copyright......Page 8
Dedication......Page 9
Contents......Page 11
Introduction to the Tenth Anniversary Edition......Page 19
Afterword to the Tenth Anniversary Edition......Page 21
Structure of the book......Page 23
How to use this book......Page 26
Acknowledgements......Page 29
Linear algebra and quantum mechanics......Page 31
Frequently used quantum gates and circuit symbols......Page 32
1.1 Global perspectives......Page 35
1.1.1 History of quantum computation and quantum information......Page 36
Any algorithmic process can be simulated efficiently using a Turing machine......Page 39
Any algorithmic process can be simulated efficiently using a probabilistic Turing machine......Page 40
1.1.2 Future directions......Page 46
1.2 Quantum bits......Page 47
1.2.1 Multiple qubits......Page 50
1.3.1 Single qubit gates......Page 51
1.3.2 Multiple qubit gates......Page 54
1.3.4 Quantum circuits......Page 56
1.3.5 Qubit copying circuit?......Page 58
1.3.6 Example: Bell states......Page 59
1.3.7 Example: quantum teleportation......Page 60
1.4 Quantum algorithms......Page 62
1.4.1 Classical computations on a quantum computer......Page 63
1.4.2 Quantum parallelism......Page 64
1.4.3 Deutsch’s algorithm......Page 66
1.4.4 The Deutsch–Jozsa algorithm......Page 68
1.4.5 Quantum algorithms summarized......Page 70
Quantum algorithms based upon the Fourier transform......Page 71
Quantum search algorithms......Page 72
Quantum simulation......Page 73
The power of quantum computation......Page 74
1.5 Experimental quantum information processing......Page 76
1.5.1 The Stern–Gerlach experiment......Page 77
1.5.2 Prospects for practical quantum information processing......Page 80
1.6 Quantum information......Page 84
Classical information through quantum channels......Page 86
Quantum information through quantum channels......Page 88
Quantum distinguishability......Page 90
History and further reading......Page 92
2 Introduction to quantum mechanics......Page 94
2.1 Linear algebra......Page 95
2.1.1 Bases and linear independence......Page 96
2.1.2 Linear operators and matrices......Page 97
2.1.4 Inner products......Page 99
2.1.5 Eigenvectors and eigenvalues......Page 102
2.1.6 Adjoints and Hermitian operators......Page 103
2.1.7 Tensor products......Page 105
2.1.8 Operator functions......Page 109
2.1.9 The commutator and anti-commutator......Page 110
2.1.10 The polar and singular value decompositions......Page 112
2.2.1 State space......Page 114
2.2.2 Evolution......Page 115
2.2.3 Quantum measurement......Page 118
2.2.4 Distinguishing quantum states......Page 120
2.2.5 Projective measurements......Page 121
2.2.6 POVM measurements......Page 124
2.2.8 Composite systems......Page 127
2.2.9 Quantum mechanics: a global view......Page 130
2.3 Application: superdense coding......Page 131
2.4 The density operator......Page 132
2.4.1 Ensembles of quantum states......Page 133
2.4.2 General properties of the density operator......Page 135
2.4.3 The reduced density operator......Page 139
2.5 The Schmidt decomposition and purifications......Page 143
2.6 EPR and the Bell inequality......Page 145
History and further reading......Page 152
3 Introduction to computer science......Page 154
3.1.1 Turing machines......Page 156
3.1.2 Circuits......Page 163
3.2 The analysis of computational problems......Page 169
3.2.1 How to quantify computational resources......Page 170
Asymptotic notation: examples......Page 171
3.2.2 Computational complexity......Page 172
3.2.3 Decision problems and the complexity classes P and NP......Page 175
3.3 Perspectives on computer science......Page 195
History and further reading......Page 201
4 Quantum circuits......Page 205
4.1 Quantum algorithms......Page 206
4.2 Single qubit operations......Page 208
4.3 Controlled operations......Page 211
4.4 Measurement......Page 219
4.5 Universal quantum gates......Page 222
4.5.1 Two-level unitary gates are universal......Page 223
4.5.2 Single qubit and CNOT gates are universal......Page 225
Universality of Hadamard + phase…......Page 228
4.5.4 Approximating arbitrary unitary gates is generically hard......Page 232
4.5.5 Quantum computational complexity......Page 234
4.6 Summary of the quantum circuit model of computation......Page 236
4.7.1 Simulation in action......Page 238
4.7.2 The quantum simulation algorithm......Page 240
4.7.3 An illustrative example......Page 243
4.7.4 Perspectives on quantum simulation......Page 245
History and further reading......Page 248
5 The quantum Fourier transform and its applications......Page 250
5.1 The quantum Fourier transform......Page 251
5.2 Phase estimation......Page 255
5.2.1 Performance and requirements......Page 257
5.3.1 Application: order-finding......Page 260
Performance......Page 263
5.3.2 Application: factoring......Page 266
5.4 General applications of the quantum Fourier transform......Page 268
5.4.1 Period-finding......Page 270
5.4.2 Discrete logarithms......Page 272
5.4.3 The hidden subgroup problem......Page 274
5.4.4 Other quantum algorithms?......Page 276
History and further reading......Page 279
6.1.1 The oracle......Page 282
6.1.2 The procedure......Page 284
6.1.3 Geometric visualization......Page 286
6.1.4 Performance......Page 287
6.2 Quantum search as a quantum simulation......Page 289
6.3 Quantum counting......Page 295
6.4 Speeding up the solution of NP-complete problems......Page 297
6.5 Quantum search of an unstructured database......Page 299
6.6 Optimality of the search algorithm......Page 303
6.7 Black box algorithm limits......Page 305
History and further reading......Page 310
7.1 Guiding principles......Page 311
7.2.1 Representation of quantum information......Page 313
7.2.3 Preparation of fiducial initial states......Page 315
7.2.4 Measurement of output result......Page 316
7.3.1 Physical apparatus......Page 317
7.3.2 The Hamiltonian......Page 318
7.3.4 Drawbacks......Page 320
7.4.1 Physical apparatus......Page 321
7.4.2 Quantum computation......Page 324
7.4.3 Drawbacks......Page 330
7.5 Optical cavity quantum electrodynamics......Page 331
Two-level atoms......Page 332
7.5.2 The Hamiltonian......Page 334
7.5.3 Single-photon single-atom absorption and refraction......Page 337
7.5.4 Quantum computation......Page 340
Optical cavity quantum electrodynamics......Page 342
Trap geometry and lasers......Page 343
Atomic structure......Page 347
7.6.2 The Hamiltonian......Page 351
Controlled phase-flip gate......Page 353
Swap gate......Page 354
Controlled-NOT gate......Page 355
7.7 Nuclear magnetic resonance......Page 358
7.7.1 Physical apparatus......Page 359
Single spin dynamics......Page 360
Thermal equilibrium......Page 362
Decoherence......Page 363
Refocusing......Page 365
Controlled-NOT gate......Page 366
Temporal, spatial, and logical labeling......Page 367
Ensemble readout of quantum algorithm results......Page 369
State tomography......Page 370
Quantum logic gates......Page 371
Quantum algorithms......Page 373
Drawbacks......Page 374
7.8 Other implementation schemes......Page 377
History and further reading......Page 383
8 Quantum noise and quantum operations......Page 387
8.1 Classical noise and Markov processes......Page 388
8.2.1 Overview......Page 390
8.2.2 Environments and quantum operations......Page 391
8.2.3 Operator-sum representation......Page 394
Physical interpretation of the operator-sum representation......Page 396
Measurements and the operator-sum representation......Page 397
System–environment models for any operator-sum representation......Page 399
8.2.4 Axiomatic approach to quantum operations......Page 400
Freedom in the operator-sum representation......Page 404
8.3 Examples of quantum noise and quantum operations......Page 407
8.3.2 Geometric picture of single qubit quantum operations......Page 408
8.3.3 Bit flip and phase flip channels......Page 410
8.3.4 Depolarizing channel......Page 412
8.3.5 Amplitude damping......Page 414
8.3.6 Phase damping......Page 417
8.4.1 Master equations......Page 420
8.4.2 Quantum process tomography......Page 423
8.5 Limitations of the quantum operations formalism......Page 428
History and further reading......Page 431
9.1 Distance measures for classical information......Page 433
9.2.1 Trace distance......Page 437
9.2.2 Fidelity......Page 443
9.2.3 Relationships between distance measures......Page 449
9.3 How well does a quantum channel preserve information?......Page 450
Quantum sources of information and the entanglement fidelity......Page 453
History and further reading......Page 458
10 Quantum error-correction......Page 459
10.1 Introduction......Page 460
10.1.1 The three qubit bit flip code......Page 461
Improving the error analysis......Page 463
10.1.2 Three qubit phase flip code......Page 464
10.2 The Shor code......Page 466
10.3 Theory of quantum error-correction......Page 469
10.3.1 Discretization of the errors......Page 472
10.3.2 Independent error models......Page 475
10.3.4 The quantum Hamming bound......Page 478
10.4.1 Classical linear codes......Page 479
10.4.2 Calderbank–Shor–Steane codes......Page 484
The Steane code......Page 486
10.5 Stabilizer codes......Page 487
10.5.1 The stabilizer formalism......Page 488
10.5.2 Unitary gates and the stabilizer formalism......Page 493
10.5.3 Measurement in the stabilizer formalism......Page 497
10.5.5 Stabilizer code constructions......Page 498
The three qubit bit flip code......Page 501
The five qubit code......Page 502
CSS codes and the seven qubit code......Page 503
10.5.7 Standard form for a stabilizer code......Page 504
10.5.8 Quantum circuits for encoding, decoding, and correction......Page 506
10.6 Fault-tolerant quantum computation......Page 508
10.6.1 Fault-tolerance: the big picture......Page 509
Fault-tolerant operations: definitions......Page 510
Example: fault-tolerant controlled-NOT......Page 512
Concatenated codes and the threshold theorem......Page 514
Normalizer operations......Page 516
Fault-tolerant π/8 gate......Page 519
10.6.3 Fault-tolerant measurement......Page 523
Measurement of stabilizer generators......Page 526
10.6.4 Elements of resilient quantum computation......Page 527
History and further reading......Page 531
11.1 Shannon entropy......Page 534
11.2.1 The binary entropy......Page 536
11.2.2 The relative entropy......Page 538
11.2.3 Conditional entropy and mutual information......Page 539
11.2.4 The data processing inequality......Page 543
11.3 Von Neumann entropy......Page 544
11.3.1 Quantum relative entropy......Page 545
11.3.2 Basic properties of entropy......Page 547
11.3.3 Measurements and entropy......Page 548
11.3.4 Subadditivity......Page 549
11.3.5 Concavity of the entropy......Page 550
11.3.6 The entropy of a mixture of quantum states......Page 552
11.4.1 Proof of strong subadditivity......Page 553
11.4.2 Strong subadditivity: elementary applications......Page 556
History and further reading......Page 560
12 Quantum information theory......Page 562
12.1 Distinguishing quantum states and the accessible information......Page 563
12.1.1 The Holevo bound......Page 565
12.2 Data compression......Page 570
12.2.1 Shannon’s noiseless channel coding theorem......Page 571
12.2.2 Schumacher’s quantum noiseless channel coding theorem......Page 576
12.3 Classical information over noisy quantum channels......Page 580
Random coding for the binary symmetric channel......Page 582
Shannon’s noisy channel coding theorem......Page 585
12.3.2 Communication over noisy quantum channels......Page 588
Random coding......Page 589
Proof of the upper bound......Page 592
Examples......Page 594
12.4.1 Entropy exchange and the quantum Fano inequality......Page 595
12.4.2 The quantum data processing inequality......Page 598
12.4.3 Quantum Singleton bound......Page 602
12.4.4 Quantum error-correction, refrigeration and Maxwell’s demon......Page 603
12.5 Entanglement as a physical resource......Page 605
12.5.1 Transforming bi-partite pure state entanglement......Page 607
12.5.2 Entanglement distillation and dilution......Page 612
12.5.3 Entanglement distillation and quantum error-correction......Page 614
12.6.1 Private key cryptography......Page 616
12.6.2 Privacy amplification and information reconciliation......Page 618
CSS code privacy amplification & information reconciliation......Page 619
12.6.3 Quantum key distribution......Page 620
The BB84 protocol......Page 621
The B92 protocol......Page 623
12.6.4 Privacy and coherent information......Page 626
12.6.5 The security of quantum key distribution......Page 627
Random sampling can upper-bound eavesdropping......Page 628
The modified Lo–Chau protocol......Page 629
A quantum error-correction protocol......Page 631
Reduction to BB84......Page 633
History and further reading......Page 638
Appendix 1: Notes on basic probability theory......Page 642
History and further reading......Page 643
A2.1 Basic definitions......Page 644
A2.1.2 Cyclic groups......Page 645
A2.2.1 Equivalence and reducibility......Page 646
A2.2.2 Orthogonality......Page 647
A2.2.3 The regular representation......Page 648
A2.3 Fourier transforms......Page 649
History and further reading......Page 650
Appendix 3: The Solovay–Kitaev theorem......Page 651
History and further reading......Page 658
A4.1 Fundamentals......Page 659
A4.2 Modular arithmetic and Euclid’s algorithm......Page 660
A4.3 Reduction of factoring to order-finding......Page 667
A4.4 Continued fractions......Page 669
History and further reading......Page 673
Appendix 5: Public key cryptography and the RSA cryptosystem......Page 674
History and further reading......Page 678
Appendix 6: Proof of Lieb’s theorem......Page 679
History and further reading......Page 682
Bibliography......Page 683
Index......Page 699