1 Probability basics 1
1.1 Events,event space,and probabilities 1
1.2 Combinatorics 8
1.3 Combined,joint,and conditional probabilities 11
1.4 Exercises 18
2 Probability distributions 20
2.1 Mean and variance 20
2.2 Exponential,Poisson,and binomial distributions 22
2.3 Continuous distributions 26
2.4 Uniform,exponential,and Gaussian(normal)distributions 26
2.5 Central-limit theorem 33
2.6 Exercises 35
3 Measuring information 37
3.1 Making sense of information 38
3.2 Measuring information 40
3.3 Information bits 43
3.4 Rényi'sfake coin 45
3.5 Exercises 49
4 Entropy 50
4.1 From Boltzmann to Shannon 50
4.2 Entropyindice 53
4.3 Language entropy 57
4.4 Maximum entropy(discrete source) 63
4.5 Exercises 67
5 Mutual information and more entropies 69
5.1 Joint and conditional entropies 69
5.2 Mutual information 75
5.3 Relative entropy 79
5.4 Exercises 82
6 Differential entropy 84
6.1 Entropy of continuous sources 84
6.2 Maximum entropy(continuous source) 90
6.3 Exercises 94
7 Algorithmic entropy and Kolmogorov complexity 96
7.1 Defining algorithmic entropy 96
7.2 The Turingmachine 97
7.3 Universal Turing machine 107
7.4 Kolmogorov complexity 111
7.5 Kolmogorov complexity vs.Shannon's entropy 123
7.6 Exercises 125
8 Information coding 127
8.1 Coding numbers 127
8.2 Coding language 129
8.3 The Morse code 132
8.4 Mean code length and coding efficiency 136
8.5 Optimizing coding efficiency 138
8.6 Shannon's source-coding theorem 142
8.7 Exercises 149
9 Optimal coding and compression 151
9.1 Huffman codes 151
9.2 Data compression 156
9.3 Block codes 162
9.4 Exercises 177
10 Integer,arithmetic,and adaptive coding 179
10.1 Integer coding 179
10.2 Arithmetic coding 185
10.3 Adaptive Huffman coding 192
10.4 Lempel-Ziv coding 200
10.5 Exercises 207
11 Error correction 208
11.1 Communication channel 208
11.2 Linear block codes 210
11.3 Cyclic codes 217
11.4 Error-correction code types 219
11.5 Corrected bit-error-rate 226
11.6 Exercises 230
12 Channel entropy 232
12.1 Binary symmetric channel 232
12.2 Nonbinary and asymmetric discrete channels 234
12.3 Channel entropy and mutual information 238
12.4 Symbol error rate 242
12.5 Exercises 244
13 Channel capacity and coding theorem 245
13.1 Channel capacity 245
13.2 Typical sequences and the typical set 252
13.3 Shannon's channel coding theorem 255
13.4 Exercises 263
14 Gaussian channel and Shannon-Hartley theorem 264
14.1 Gaussian channel 264
14.2 Nonlinear channel 277
14.3 Exercises 282
15 Reversible computation 283
15.1 Maxwell's demon and Landauer's principle 283
15.2 From computer architecture to logic gates 288
15.3 Reversible logic gates and computation 297
15.4 Exercises 302
16 Quantum bits and quantum gates 304
16.1 Quantum bits 304
16.2 Basic computations with 1-qubit quantum gates 310
16.3 Quantum gates with multiple qubit inputs and outputs 315
16.4 Quantum circuits 322
16.5 Tensor products 327
16.6 Noncloning theorem 330
16.7 Exercises 331
17 Quantum measurements 333
17.1 Dirac notation 333
17.2 Quantum measurements and types 343
17.3 Quantum measurements on joint states 351
17.4 Exercises 355
18 Qubit measurements,superdense coding,and quantum teleportation 356
18.1 Measuring single qubits 356
18.2 Measuring n-qubits 361
18.3 Bell state measurement 365
18.4 Superdense coding 366
18.5 Quantum teleportation 367
18.6 Distributed quantum computing 374
18.7 Exercises 376
19 Deutsch-Jozsa,quantum Fourier transform,and Grover quantum database search algorithms 378
19.1 Deutsch algorithm 378
19.2 Deutsch-Jozsa algorithm 381
19.3 Quantum Fourier transform algorithm 383
19.4 Grover quantum database search algorithm 389
19.5 Exercises 398
20 Shor's factorization algorithm 399
20.1 Phase estimation 400
20.2 Order finding 405
20.3 Continued fraction expansion 408
20.4 From order finding to factorization 410
20.5 Shor's factorization algorithm 415
20.6 Factorizing N=15 and other nontrivial composites 417
20.7 Public-key cryptography 424
20.8 Exercises 429
21 Quantum information theory 431
21.1 Von Neumann entropy 431
21.2 Relative,joint,and conditional entropy,and mutual information 437
21.3 Quantum communication channel and Holevo bound 450
21.4 Exercises 454
22 Quantum data compression 457
22.1 Quantum data compression and fidelity 457
22.2 Schumacher's quantum coding theorem 464
22.3 A graphical and numerical illustration of Schumacher's quantum coding theorem 469
22.4 Exercises 474
23 Quantum channel noise and channel capacity 475
23.1 Noisy quantum channels 475
23.2 The Holevo-Schumacher-Westmoreland capacity theorem 481
23.3 Capacity of some quantum channels 487
23.4 Exercises 493
24 Quantum error correction 496
24.1 Quantum repetition code 496
24.2 Shor code 503
24.3 Calderbank-Shor-Steine(CSS)codes 509
24.4 Hadamard-Steane code 514
24.5 Exercises 521
25 Classical and quantum cryptography 523
25.1 Message encryption,decryption,and code breaking 524
25.2 Encryption and decryption with binary numbers 527
25.3 Double-key encryption 532
25.4 Cryptography without key exchange 534
25.5 Public-key cryptography and RSA 536
25.6 Data encryption standard(DES)and advanced encryption standard(AES) 541
25.7 Quantum cryptography 543
25.8 Electromagnetic waves,polarization states,photons,and quantum measurements 544
25.9 A secure photon communication channel 554
25.10 The BB84 protocol for QKD 556
25.11 The B92 protocol 558
25.12 The EPR protocol 559
25.13 Is quantum cryptography"invulnerable?" 562
Appendix A(Chapter 4)Boltzmann's entropy 565
Appendix B(Chapter 4)Shannon's entropy 568
Appendix C(Chapter 4)Maximum entropy of discrete sources 573
Appendix D(Chapter 5)Markov chains and the second law of thermodynamics 581
Appendix E(Chapter 6) From discrete to continuous entropy 587
Appendix F(Chapter 8)Kraft-McMillan inequality 589
Appendix G(Chapter 9)Overview of data compression standards 591
Appendix H(Chapter 10)Arithmetic coding algorithm 605
Appendix I(Chapter 10)Lempel-Ziv distinctparsing 610
Appendix J(Chapter 11)Error-correction capability of linear block codes 614
Appendix K(Chapter 13)Capacity of binary communication channels 617
Appendix L(Chapter 13)Converse proof of the channel codingtheorem 62lAppendix M(Chapter 16)Bloch sphere representation of the qubit 625
Appendix N(Chapter 16)Pauli matrices,rotations,and unitary operators 627
Appendix O(Chapter 17)Heisenberg uncertainty principle 635
Appendix P(Chapter 18)Two-qubit teleportation 637
Appendix Q(Chapter 19)Quantum Fourier transform circuit 644
Appendix R(Chapter 20)Properties of continued fraction expansion 648
Appendix S(Chapter 20)Computation of inverse Fourier transform in the factorization of N=21 through Shor's algorithm 653
Appendix T(Chapter 20)Modular arithmetic and Euler's theorem 656
Appendix U(Chapter 21)Klein's inequality 660
Appendix V(Chapter 21)Schmidt decomposition of joint pure states 662
Appendix W(Chapter 21)Statepurification 664
Appendix X(Chapter 21)Holevo bound 666
Appendix Y(Chapter 25)Polynomial byte representation and modular multiplication 672
Index 676