Quantum Computing and Communications: An Engineering Approach

Cover......Page 1
Title page......Page 4
Copyright, ISBN 047086902X......Page 5
Dedication......Page 6
Contents......Page 8
Preface......Page 14
How to use this book......Page 16
Acknowledgments......Page 18
List of Figures......Page 20
Acronyms......Page 26
Part-I: Introduction to QuantumComputing......Page 30
1.1 Life Cycle of a Well-known Invention......Page 32
1.2 What about Computers and Computing?......Page 33
1.3 Let us Play Marbles......Page 36
2.1 Mystery of Probabilistic √I Gate......Page 38
2.2 The Postulates of Quantum Mechanics......Page 43
2.3 Qbits and Qregisters......Page 46
2.4 Elementary Quantum Gates......Page 50
2.5 General Description of the Interferometer......Page 53
2.6.1 A surprising quantum state – entanglement......Page 56
2.6.2 The CNOT gate as classical copy machine and\rquantum entangler......Page 57
2.6.3 Bell states......Page 59
2.6.4 Entanglement with the environment – decoherence......Page 61
2.6.5 The EPR paradox and the Bell inequality......Page 64
2.7 No Cloning Theorem......Page 69
2.8 How to Prepare an Arbitrary Superposition......Page 71
2.9 Further Reading......Page 72
3.1 General Measurements......Page 74
3.2 Projective Measurements......Page 75
3.2.1 Measurement operators and the 3rd Postulate\rin the case of projective measurement......Page 76
3.2.2 Measurement using the computational basis states......Page 78
3.2.4 Repeated projective measurement......Page 79
3.2.5 CHSH inequality with entangled particles......Page 80
3.3 Positive Operator Valued Measurement......Page 81
3.3.1 Measurement operators and the 3rd Postulate in the case ofPOVM......Page 83
3.3.2 How to apply POVM operators......Page 85
3.4 Relations among the Measurement Types......Page 87
3.5 Quantum Computing-based Solution of the Game\rwith Marbles......Page 88
3.6 Further Reading......Page 90
Part-II: Quantum Algorithms......Page 92
4.1 Superdense Coding......Page 94
4.2 Quantum Teleportation......Page 96
4.3 Further Reading......Page 99
5.1 Introduction......Page 100
5.2 Deutsch–Jozsa Algorithm......Page 103
5.3 Simon Algorithm......Page 107
5.4 Further Reading......Page 110
6. Quantum Fourier Transform and its Applications......Page 112
6.1 Quantum Fourier Transform......Page 113
6.2.1 Idealistic phase estimation......Page 117
6.2.2 Phase estimation in practical cases......Page 119
6.2.3 Quantitative analysis of the phase estimator......Page 123
6.2.4 Estimating quantum uncertainty......Page 125
6.3.1 Connection between factoring and order finding......Page 131
6.3.2 Quantum-based order finding......Page 133
6.3.3 Error analysis and a numerical example......Page 138
6.4 QFT as generalized Hadamard transform......Page 142
6.5.1 Period finding......Page 146
6.5.2 Two-dimensional period finding and discrete logarithm......Page 147
6.6 Further Reading......Page 150
Part-III: Quantum-assisted Solutions of Infocom Problems......Page 154
7. Searching in an Unsorted Database......Page 156
7.1.1 Initialization – quantum parallelism......Page 157
7.1.2 First stage of G – the Oracle......Page 159
7.1.3 Second stage of G – inversion about the average......Page 160
7.1.4 Required number of iterations......Page 163
7.1.5 Error analysis......Page 166
7.2.1 Quantum counting based on phase estimation......Page 169
7.2.2 Error analysis......Page 171
7.2.3 Replacing quantum counting with indirect estimation onM......Page 176
7.3 Quantum Existence Testing......Page 178
7.3.1 Error analysis......Page 180
7.4 Finding Extreme Values in an Unsorted Database......Page 182
7.5.1 Generalization of the basic Grover database search algorithm......Page 184
7.5.2 Required number of iterations in the generalized Groveralgorithm......Page 188
7.5.3 Design considerations of the generalized Grover operator......Page 193
7.6 Further Reading......Page 197
8.1 Introduction to Code Division Multiple Access and\rClassical Multi-user Detection......Page 200
8.1.1 DS-CDMA in theory......Page 202
8.1.2 DS-CDMA in practice......Page 203
8.2 Optimal Multi-user Detection......Page 208
8.3 Quantum-based Multi-user Detection......Page 212
8.4 Further Reading......Page 214
9.1 Introduction to Cryptology......Page 216
9.2 Symmetric Key Cryptography......Page 218
9.2.1 Large number of users......Page 219
9.2.2 Length of the key and its randomness......Page 220
9.3 Public Key Cryptography......Page 221
9.3.1 The RSA algorithm......Page 223
9.3.2 Digital signatures......Page 224
9.4.1 Using Grover’s database search algorithm to break RSA......Page 226
9.4.2 Using Shor’s order finding algorithm to break RSA......Page 227
9.5 Further Reading......Page 229
10.1 The BB84 Protocol......Page 232
10.1.1 Idealistic scenario......Page 233
10.1.2 Eve appears on the scene......Page 235
10.1.3 When the channel introduces errors......Page 236
10.2 The B92 Algorithm......Page 237
10.4 Teleportation as a Useful Element in Quantum\rCryptography......Page 239
10.5 Further Reading......Page 240
11.1 Introduction to WEB Surfing......Page 244
11.2 Quantum-based Solution of the Guessing Secret\rProblem......Page 247
Part-IV: Appendices......Page 252
12.1.1 Characterization of random events......Page 254
12.1.2 Decision theory......Page 256
12.2.2 Gaussian elimination......Page 257
12.2.3 Vector spaces......Page 258
12.2.5 Special linear operators......Page 261
12.3.1 Modular arithmetic......Page 263
12.3.2 Definitions......Page 264
12.3.3 Euclid’s algorithm......Page 265
12.3.4 Continued fraction and convergents......Page 266
12.3.5 Useful theorems......Page 268
13.1 Eigenvalues of the Generalized Grover Operator......Page 270
13.2 Eigenvectors of the Generalized Grover Operator......Page 272
14. Complex Baseband-equivalent Description of Bandlimited\rSignals......Page 276
15. Useful Links......Page 278
References......Page 280
Solutions of Exercises......Page 292
Index......Page 310