Quantum computing and communications : an engineering approach /

Contents 9
Preface 15
How to use this book 17
Acknowledgments 19
List of Figures 21
Acronyms 27
Part I Introduction to Quantum Computing 31
1 Motivations 33
1.1 Life Cycle of a Well-known Invention 33
1.2 What about Computers and Computing? 34
1.3 Let us Play Marbles 37
2 Quantum Computing Basics 39
2.1 Mystery of Probabilistic Gate 39
2.2 The Postulates of Quantum Mechanics 44
2.3 Qbits and Qregisters 47
2.4 Elementary Quantum Gates 51
2.5 General Description of the Interferometer 54
2.6 Entanglement 57
2.6.1 A surprising quantum state \u2013 entanglement 57
2.6.2 The CNOT gate as classical copy machine and quantum entangler 58
2.6.3 Bell states 60
2.6.4 Entanglement with the environment \u2013 decoherence 62
2.6.5 The EPR paradox and the Bell inequality 65
2.7 No Cloning Theorem 70
2.8 How to Prepare an Arbitrary Superposition 72
2.9 Further Reading 73
3 Measurements 75
3.1 General Measurements 75
3.2 Projective Measurements 76
3.2.1 Measurement operators and the 3rd Postulate in the case of projective measurement 77
3.2.2 Measurement using the computational basis states 79
3.2.3 Observable and projective measurement 80
3.2.4 Repeated projective measurement 80
3.2.5 CHSH inequality with entangled particles 81
3.3 Positive Operator Valued Measurement 82
3.3.1 Measurement operators and the 3rd Postulate in the case of POVM 84
3.3.2 How to apply POVM operators 86
3.4 Relations among the Measurement Types 88
3.5 Quantum Computing-based Solution of the Game with Marbles 89
3.6 Further Reading 91
Part II Quantum Algorithms 93
4 Two Simple Quantum Algorithms 95
4.1 Superdense Coding 95
4.2 Quantum Teleportation 97
4.3 Further Reading 100
5 Quantum Parallelism 101
5.1 Introduction 101
5.2 Deutsch\u2013Jozsa Algorithm 104
5.3 Simon Algorithm 108
5.4 Further Reading 111
6 Quantum Fourier Transform and its Applications 113
6.1 Quantum Fourier Transform 114
6.2 Quantum Phase Estimation 118
6.2.1 Idealistic phase estimation 118
6.2.2 Phase estimation in practical cases 120
6.2.3 Quantitative analysis of the phase estimator 124
6.2.4 Estimating quantum uncertainty 126
6.3 Order Finding and Factoring \u2013 Shor Algorithm 132
6.3.1 Connection between factoring and order finding 132
6.3.2 Quantum-based order finding 134
6.3.3 Error analysis and a numerical example 139
6.4 QFT as generalized Hadamard transform 143
6.5 Generalizations of order finding 147
6.5.1 Period finding 147
6.5.2 Two-dimensional period finding and discrete logarithm 148
6.6 Further Reading 151
Part III Quantum-assisted Solutions of Infocom Problems 155
7 Searching in an Unsorted Database 157
7.1 The Basic Grover Algorithm 158
7.1.1 Initialization \u2013 quantum parallelism 158
7.1.2 First stage of G \u2013 the Oracle 160
7.1.3 Second stage of G \u2013 inversion about the average 161
7.1.4 Required number of iterations 164
7.1.5 Error analysis 167
7.2 Quantum Counting 170
7.2.1 Quantum counting based on phase estimation 170
7.2.2 Error analysis 172
7.2.3 Replacing quantum counting with indirect estimation on M 177
7.3 Quantum Existence Testing 179
7.3.1 Error analysis 181
7.4 Finding Extreme Values in an Unsorted Database 183
7.5 The Generalized Grover Algorithm 185
7.5.1 Generalization of the basic Grover database search algorithm 185
7.5.2 Required number of iterations in the generalized Grover algorithm 189
7.5.3 Design considerations of the generalized Grover operator 194
7.6 Further Reading 198
8 Quantum-based Multi-user Detection 201
8.1 Introduction to Code Division Multiple Access and Classical Multi-user Detection 201
8.1.1 DS-CDMA in theory 203
8.1.2 DS-CDMA in practice 204
8.2 Optimal Multi-user Detection 209
8.3 Quantum-based Multi-user Detection 213
8.4 Further Reading 215
9 Quantum-based Code Breaking 217
9.1 Introduction to Cryptology 217
9.2 Symmetric Key Cryptography 219
9.2.1 Large number of users 220
9.2.2 Length of the key and its randomness 221
9.3 Public Key Cryptography 222
9.3.1 The RSA algorithm 224
9.3.2 Digital signatures 225
9.4 Quantum-based Solutions for Breaking Public Key Cryptosystems 227
9.4.1 Using Grover\u2019s database search algorithm to break RSA 227
9.4.2 Using Shor\u2019s order finding algorithm to break RSA 228
9.5 Further Reading 230
10 Quantum-based Key Distribution 233
10.1 The BB84 Protocol 234
10.1.1 Idealistic scenario 234
10.1.2 Eve appears on the scene 236
10.1.3 When the channel introduces errors 237
10.2 The B92 Algorithm 238
10.3 EPR Paradox Based Key Distribution 240
10.4 Teleportation as a Useful Element in Quantum Cryptography 240
10.5 Further Reading 241
11 Surfing the WEB on Quantum Basis 245
11.1 Introduction to WEB Surfing 245
11.2 Quantum-based Solution of the Guessing Secret Problem 248
Part IV Appendices 253
12 Mathematical Background 255
12.1 Basic Probability Theory 255
12.1.1 Characterization of random events 255
12.1.2 Decision theory 257
12.2 Linear Algebra 258
12.2.1 Complex numbers 258
12.2.2 Gaussian elimination 258
12.2.3 Vector spaces 259
12.2.4 Eigenvectors and eigenvalues 262
12.2.5 Special linear operators 262
12.2.6 Operator functions 264
12.3 Number Theory 264
12.3.1 Modular arithmetic 264
12.3.2 Definitions 265
12.3.3 Euclid\u2019s algorithm 266
12.3.4 Continued fraction and convergents 267
12.3.5 Useful theorems 269
13 Derivations Related to the Generalized Grover Algorithm 271
13.1 Eigenvalues of the Generalized Grover Operator 271
13.2 Eigenvectors of the Generalized Grover Operator 273
14 Complex Baseband-equivalent Description of Bandlimited Signals 277
15 Useful Links 279
References 281
Solutions of Exercises 293
Index 311