Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Foreword......Page 13
Introduction......Page 19
Acknowledgments......Page 23
1.1 Events, event space, and probabilities......Page 25
Rolling dice (game 2)......Page 28
Arranging books on a shelf......Page 32
Fruit-market shopping......Page 34
1.3 Combined, joint, and conditional probabilities......Page 35
Taking exams......Page 37
Sharing birthdays......Page 38
Party meetings......Page 39
Drawing cards......Page 40
1.4 Exercises......Page 42
2.1 Mean and variance......Page 44
2.2 Exponential, Poisson, and binomial distributions......Page 46
2.4 Uniform, exponential, and Gaussian (normal) distributions......Page 50
2.5 Central-limit theorem......Page 57
Rolling dice and adding spots......Page 58
2.6 Exercises......Page 59
3 Measuring information......Page 61
3.1 Making sense of information......Page 62
3.2 Measuring information......Page 64
A lotto surprise......Page 65
3.3 Information bits......Page 67
3.4 Rényi's fake coin......Page 69
3.5 Exercises......Page 73
4.1 From Boltzmann to Shannon......Page 74
4.2 Entropy in dice......Page 77
Two-dice roll......Page 78
The 421......Page 79
4.3 Language entropy......Page 81
4.4 Maximum entropy (discrete source)......Page 87
4.5 Exercises......Page 91
5.1 Joint and conditional entropies......Page 93
Stock exchange......Page 95
5.2 Mutual information......Page 99
5.3 Relative entropy......Page 103
5.4 Exercises......Page 106
6.1 Entropy of continuous sources......Page 108
6.2 Maximum entropy (continuous source)......Page 114
6.3 Exercises......Page 118
7.1 Defining algorithmic entropy......Page 120
7.2 The Turing machine......Page 121
Example 7.1......Page 123
Example 7.2......Page 124
Example 7.3......Page 125
Example 7.4......Page 126
Example 7.5......Page 127
7.3 Universal Turing machine......Page 131
7.4 Kolmogorov complexity......Page 135
Example 7.7......Page 136
Example 7.8......Page 137
Example 7.9......Page 138
7.5 Kolmogorov complexity vs. Shannon's entropy......Page 147
7.6 Exercises......Page 149
8.1 Coding numbers......Page 151
8.2 Coding language......Page 153
8.3 The Morse code......Page 156
8.4 Mean code length and coding efficiency......Page 160
8.5 Optimizing coding efficiency......Page 162
8.6 Shannons source-coding theorem......Page 166
8.7 Exercises......Page 173
9.1 Huffman codes......Page 175
9.2 Data compression......Page 180
9.3 Block codes......Page 186
Example 9.1: Four-event source......Page 187
Example 9.2: 26-event source; the English-language characters......Page 189
Example 9.3: Two-event source; the roulette game......Page 194
9.4 Exercises......Page 201
10.1 Integer coding......Page 203
10.2 Arithmetic coding......Page 209
10.3 Adaptive Huffman coding......Page 216
10.4 Lempel–Ziv coding......Page 224
10.5 Exercises......Page 231
11.1 Communication channel......Page 232
11.2 Linear block codes......Page 234
11.3 Cyclic codes......Page 241
11.4 Error-correction code types......Page 243
Golay code......Page 244
Bose–Chaudhuri–Hocquenghem (BCH) codes......Page 245
Concatenated block codes......Page 246
Convolutional codes......Page 247
Turbo codes......Page 248
11.5 Corrected bit-error-rate......Page 250
11.6 Exercises......Page 254
12.1 Binary symmetric channel......Page 256
Example 12.1: Z channel......Page 258
Example 12.2: Binary erasure channel......Page 259
Example 12.4: Asymmetric channel with nonoverlapping outputs......Page 260
12.3 Channel entropy and mutual information......Page 262
12.4 Symbol error rate......Page 266
12.5 Exercises......Page 268
13.1 Channel capacity......Page 269
Example 13.1: Z channel......Page 273
Example 13.3: Noisy typewriter......Page 274
Example 13.4: Asymmetric channel with nonoverlapping outputs......Page 275
13.2 Typical sequences and the typical set......Page 276
13.3 Shannons channel coding theorem......Page 279
Approach 1......Page 282
Approach 2......Page 283
Approach 3......Page 284
13.4 Exercises......Page 287
14.1 Gaussian channel......Page 288
Nonreturn-to-zero (NRZ) format......Page 296
M-ary phase-shift-keying (M-PSK) format......Page 298
M-ary quadrature amplitude modulation (M-QAM) format......Page 299
14.2 Nonlinear channel......Page 301
14.3 Exercises......Page 306
15.1 Maxwells demon and Landauer's principle......Page 307
15.2 From computer architecture to logic gates......Page 312
15.3 Reversible logic gates and computation......Page 321
15.4 Exercises......Page 326
16.1 Quantum bits......Page 328
16.2 Basic computations with 1-qubit quantum gates......Page 334
Pauli matrices or I, X, Y, Z-gates......Page 336
Hadamard matrix gate or H-gate......Page 338
16.3 Quantum gates with multiple qubit inputs and outputs......Page 339
CNOT gate......Page 340
CROSSOVER or SWAP gate......Page 342
Controlled-U gates......Page 343
Toffoli or CCNOT gate......Page 344
Controlled-controlled-U or CCU gate......Page 345
16.4 Quantum circuits......Page 346
16.5 Tensor products......Page 351
16.6 Noncloning theorem......Page 354
16.7 Exercises......Page 355
17.1 Dirac notation......Page 357
Inner product......Page 358
Projection operators......Page 360
Operator matrix elements......Page 361
Eigenvalues and eigenstates......Page 362
Matrix trace......Page 364
Density operator or matrix......Page 365
17.2 Quantum measurements and types......Page 367
Quantum measurements in the orthonormal basis......Page 369
Projective or von-Neumann measurements......Page 370
POVM measurements......Page 372
17.3 Quantum measurements on joint states......Page 375
17.4 Exercises......Page 379
18.1 Measuring single qubits......Page 380
18.2 Measuring n-qubits......Page 385
18.3 Bell state measurement......Page 389
18.4 Superdense coding......Page 390
18.5 Quantum teleportation......Page 391
18.6 Distributed quantum computing......Page 398
18.7 Exercises......Page 400
19.1 Deutsch algorithm......Page 402
19.2 Deutsch–Jozsa algorithm......Page 405
19.3 Quantum Fourier transform algorithm......Page 407
19.4 Grover quantum database search algorithm......Page 413
19.5 Exercises......Page 422
20 Shor's factorization algorithm......Page 423
20.1 Phase estimation......Page 424
20.2 Order finding......Page 429
20.3 Continued fraction expansion......Page 432
Discussion......Page 433
20.4 From order finding to factorization......Page 434
20.5 Shor's factorization algorithm......Page 439
Shor's algorithm......Page 440
20.6 Factorizing N = 15 and other nontrivial composites......Page 441
Discussion......Page 444
20.7 Public-key cryptography......Page 448
20.8 Exercises......Page 453
21.1 Von Neumann entropy......Page 455
Composite system in pure state......Page 461
Subadditivity inequality and quantum joint entropy......Page 463
Conditional entropy......Page 465
Triangle inequality......Page 466
Concavity of entropy and entropy of system in random states......Page 467
Example 21.2: Subsystems with correlated information......Page 469
Example 21.3: Composite system in pure state......Page 472
21.3 Quantum communication channel and Holevo bound......Page 474
Example 21.4: A “useless” quantum communication channel......Page 475
Example 21.5: A quantum communication channel reduced to classical......Page 476
Example 21.6: General case......Page 477
21.4 Exercises......Page 478
22.1 Quantum data compression and fidelity......Page 481
22.2 Schumacher's quantum coding theorem......Page 488
22.3 A graphical and numerical illustration of Schumacher's quantum coding theorem......Page 493
22.4 Exercises......Page 498
23.1 Noisy quantum channels......Page 499
Depolarizing channel......Page 501
Bit-flip channel......Page 503
Bit-phase-flip channel......Page 504
23.2 The Holevo–Schumacher–Westmoreland capacity theorem......Page 505
23.3 Capacity of some quantum channels......Page 511
Example 23.1: Depolarizing channel......Page 512
Example 23.2: Bit-flip channel......Page 515
23.4 Exercises......Page 517
24.1 Quantum repetition code......Page 520
24.2 Shor code......Page 527
Phase-flip error......Page 529
Bit-flip error......Page 530
24.3 Calderbank–Shor–Steine (CSS) codes......Page 533
24.4 Hadamard–Steane code......Page 538
24.5 Exercises......Page 545
25 Classical and quantum cryptography......Page 547
25.1 Message encryption, decryption, and code breaking......Page 548
25.2 Encryption and decryption with binary numbers......Page 551
25.3 Double-key encryption......Page 556
25.4 Cryptography without key exchange......Page 558
25.5 Public-key cryptography and RSA......Page 560
25.6 Data encryption standard (DES) and advanced encryption standard (AES)......Page 565
25.7 Quantum cryptography......Page 567
25.8 Electromagnetic waves, polarization states, photons, and quantum measurements......Page 568
25.9 A secure photon communication channel......Page 578
25.10 The BB84 protocol for QKD......Page 580
25.11 The B92 protocol......Page 582
25.12 The EPR protocol......Page 583
25.13 Is quantum cryptography "invulnerable?"......Page 586
Task 1......Page 589
Task 2......Page 590
Step 1......Page 592
Step 2......Page 593
Step 3......Page 595
Uniform distribution solution......Page 597
Discrete-exponential (Bose–Einstein) distribution solution......Page 598
Maxwell–Boltzmann distribution solution......Page 600
Markov chains and their properties......Page 605
Proving the second law of thermodynamics......Page 608
Appendix E (Chapter 6) From discrete to continuous entropy......Page 611
Appendix F (Chapter 8) Kraft–McMillan inequality......Page 613
Sounds......Page 615
Datafiles......Page 620
Images......Page 622
MPEG-1......Page 625
MPEG-2......Page 626
MPEG-4......Page 627
Appendix H (Chapter 10) Arithmetic coding algorithm......Page 629
Distinct parsing......Page 634
Proof of Eq. (I3)......Page 637
Appendix J (Chapter 11) Error-correction capability of linear block codes......Page 638
Appendix K (Chapter 13) Capacity of binary communication channels......Page 641
Note......Page 643
Property A......Page 645
Property B......Page 646
Appendix M (Chapter 16) Bloch sphere representation of the qubit......Page 649
Exponential representation of complex numbers......Page 651
Exponential operator......Page 652
Rotation operators......Page 653
Euler’s theorem......Page 655
Decomposition of 2 × 2 unitary matrices......Page 656
Commutation properties of rotation operators......Page 658
Appendix O (Chapter 17) Heisenberg uncertainty principle......Page 659
Note......Page 660
Appendix P (Chapter 18) Two-qubit teleportation......Page 661
Appendix Q (Chapter 19) Quantum Fourier transform circuit......Page 668
Property 1......Page 672
Property 2......Page 673
Property 3......Page 674
Appendix S (Chapter 20) Computation of inverse Fourier transform in the factorization of N = 21 through Shor's algorithm......Page 677
Appendix T (Chapter 20) Modular arithmetic and Euler's theorem......Page 680
Appendix U (Chapter 21) Klein's inequality......Page 684
Appendix V (Chapter 21) Schmidt decomposition of joint pure states......Page 686
Appendix W (Chapter 21) State purification......Page 688
Appendix X (Chapter 21) Holevo bound......Page 690
Proof of the inequality in Eq. (X16), with discussion......Page 694
Appendix Y (Chapter 25) Polynomial byte representation and modular multiplication......Page 696
Index......Page 700