Quantum Computing Fundamentals

<p> Preface xvii</p> <p>Part I Preparatory Material</p> <p>Chapter 1: Introduction to Essential Linear Algebra 2</p> <p> 1.1 What Is Linear Algebra?.. . . . . . . . . . . . . . . . . . . . 3</p> <p> 1.2 Some Basic Algebra.. . . . . . . . . . . . . . . . . . . . . 4</p> <p> 1.3 Matrix Math.. . . . . . . . . . . . . . . . . . . . . . . . 10</p> <p> 1.4 Vectors and Vector Spaces.. . . . . . . . . . . . . . . . . . 23</p> <p> 1.5 Set Theory.. . . . . . . . . . . . . . . . . . . . . . . . . 25</p> <p> 1.6 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 29</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 29</p> <p>Chapter 2: Complex Numbers 32</p> <p> 2.1 What Are Complex Numbers?.. . . . . . . . . . . . . . . . . 32</p> <p> 2.2 Algebra of Complex Numbers.. . . . . . . . . . . . . . . . . 34</p> <p> 2.3 Complex Numbers Graphically.. . . . . . . . . . . . . . . . 38</p> <p> 2.4 Vector Representations of Complex Numbers.. . . . . . . . . . 45</p> <p> 2.5 Pauli Matrices.. . . . . . . . . . . . . . . . . . . . . . . 48</p> <p> 2.6 Transcendental Numbers.. . . . . . . . . . . . . . . . . . . 56</p> <p> 2.7 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 58</p> <p>Chapter 3: Basic Physics for Quantum Computing 60</p> <p> 3.1 The Journey to Quantum.. . . . . . . . . . . . . . . . . . . 61</p> <p> 3.2 Quantum Physics Essentials.. . . . . . . . . . . . . . . . . 65</p> <p> 3.3 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 77</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 77</p> <p>Chapter 4: Fundamental Computer Science for Quantum Computing 80</p> <p> 4.1 Data Structures.. . . . . . . . . . . . . . . . . . . . . . . 81</p> <p> 4.2 Algorithms.. . . . . . . . . . . . . . . . . . . . . . . . . 88</p> <p> 4.3 Computational Complexity.. . . . . . . . . . . . . . . . . . 93</p> <p> 4.4 Coding Theory.. . . . . . . . . . . . . . . . . . . . . . . 95</p> <p> 4.5 Logic Gates.. . . . . . . . . . . . . . . . . . . . . . . . 96</p> <p> 4.6 Computer Architecture.. . . . . . . . . . . . . . . . . . . 100</p> <p> 4.7 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 103</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 103</p> <p>Chapter 5: Basic Information Theory 106</p> <p> 5.1 Basic Probability.. . . . . . . . . . . . . . . . . . . . . . 107</p> <p> 5.2 Set Theory.. . . . . . . . . . . . . . . . . . . . . . . . 108</p> <p> 5.3 Information Theory.. . . . . . . . . . . . . . . . . . . . . 112</p> <p> 5.4 Quantum Information.. . . . . . . . . . . . . . . . . . . . 118</p> <p> 5.5 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 120</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 120</p> <p>Part II Basic Quantum Computing</p> <p>Chapter 6: Basic Quantum Theory 122</p> <p> 6.1 Further with Quantum Mechanics.. . . . . . . . . . . . . . . 123</p> <p> 6.2 Quantum Decoherence.. . . . . . . . . . . . . . . . . . . 129</p> <p> 6.3 Quantum Electrodynamics.. . . . . . . . . . . . . . . . . . 131</p> <p> 6.4 Quantum Chromodynamics.. . . . . . . . . . . . . . . . . 133</p> <p> 6.5 Feynman Diagram.. . . . . . . . . . . . . . . . . . . . . 134</p> <p> 6.6 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 136</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 136</p> <p>Chapter 7: Quantum Entanglement and QKD 138</p> <p> 7.1 Quantum Entanglement.. . . . . . . . . . . . . . . . . . . 138</p> <p> 7.2 Interpretation.. . . . . . . . . . . . . . . . . . . . . . . 143</p> <p> 7.3 QKE.. . . . . . . . . . . . . . . . . . . . . . . . . . . 146</p> <p> 7.4 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 151</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 152</p> <p>Chapter 8: Quantum Architecture 154</p> <p> 8.1 Further with Qubits.. . . . . . . . . . . . . . . . . . . . . 154</p> <p> 8.2 Quantum Gates.. . . . . . . . . . . . . . . . . . . . . . 158</p> <p> 8.3 More with Gates.. . . . . . . . . . . . . . . . . . . . . . 166</p> <p> 8.4 Quantum Circuits. . . . . . . . . . . . . . . . . . . . . . 167</p> <p> 8.5 The D-Wave Quantum Architecture.. . . . . . . . . . . . . . 169</p> <p> 8.6 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 172</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 172</p> <p>Chapter 9: Quantum Hardware 174</p> <p> 9.1 Qubits.. . . . . . . . . . . . . . . . . . . . . . . . . . 174</p> <p> 9.2 How Many Qubits Are Needed?. . . . . . . . . . . . . . . . 181</p> <p> 9.3 Addressing Decoherence.. . . . . . . . . . . . . . . . . . 182</p> <p> 9.4 Topological Quantum Computing.. . . . . . . . . . . . . . . 186</p> <p> 9.5 Quantum Essentials.. . . . . . . . . . . . . . . . . . . . 187</p> <p> 9.6 Quantum Networking.. . . . . . . . . . . . . . . . . . . . 188</p> <p> 9.7 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 191</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 191</p> <p>Chapter 10: Quantum Algorithms 194</p> <p> 10.1 What Is an Algorithm?. . . . . . . . . . . . . . . . . . . . 194</p> <p> 10.2 Deutsch’s Algorithm.. . . . . . . . . . . . . . . . . . . . 197</p> <p> 10.3 Deutsch-Jozsa Algorithm.. . . . . . . . . . . . . . . . . . 199</p> <p> 10.4 Bernstein-Vazirani Algorithm.. . . . . . . . . . . . . . . . . 201</p> <p> 10.5 Simon’s Algorithm.. . . . . . . . . . . . . . . . . . . . . 202</p> <p> 10.6 Shor’s Algorithm.. . . . . . . . . . . . . . . . . . . . . . 203</p> <p> 10.7 Grover’s Algorithm. . . . . . . . . . . . . . . . . . . . . 209</p> <p> 10.8 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 211</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 211</p> <p>Part III Quantum Computing and Cryptography</p> <p>Chapter 11: Current Asymmetric Algorithms 212</p> <p> 11.1 RSA. . . . . . . . . . . . . . . . . . . . . . . . . . . 213</p> <p> 11.2 Diffie-Hellman.. . . . . . . . . . . . . . . . . . . . . . . 216</p> <p> 11.3 Elliptic Curve.. . . . . . . . . . . . . . . . . . . . . . . 219</p> <p> 11.4 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 227</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 227</p> <p>Chapter 12: The Impact of Quantum Computing on Cryptography 228</p> <p> 12.1 Asymmetric Cryptography.. . . . . . . . . . . . . . . . . . 229</p> <p> 12.2 Specific Algorithms.. . . . . . . . . . . . . . . . . . . . . 231</p> <p> 12.3 Specific Applications. . . . . . . . . . . . . . . . . . . . 233</p> <p> 12.3.1 Digital Certificates. . . . . . . . . . . . . . . . . . 233</p> <p> 12.3.2 SSL/TLS. . . . . . . . . . . . . . . . . . . . . . 234</p> <p> 12.4 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 241</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 241</p> <p>Chapter 13: Lattice-based Cryptography 244</p> <p> 13.1 Lattice-Based Mathematical Problems.. . . . . . . . . . . . . 245</p> <p> 13.2 Cryptographic Algorithms. . . . . . . . . . . . . . . . . . 249</p> <p> 13.3 Solving Lattice Problems.. . . . . . . . . . . . . . . . . . 256</p> <p> 13.4 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 259</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 259</p> <p>Chapter 14: Multivariate Cryptography 262</p> <p> 14.1 Mathematics.. . . . . . . . . . . . . . . . . . . . . . . 262</p> <p> 14.2 Matsumoto-Imai.. . . . . . . . . . . . . . . . . . . . . . 264</p> <p> 14.3 Hidden Field Equations. . . . . . . . . . . . . . . . . . . 266</p> <p> 14.4 Multivariate Quadratic Digital Signature Scheme (MQDSS).. . . . 268</p> <p> 14.5 SFLASH.. . . . . . . . . . . . . . . . . . . . . . . . . 269</p> <p> 14.6 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 271</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 271</p> <p>Chapter 15: Other Approaches to Quantum Resistant Cryptography 274</p> <p> 15.1 Hash Functions.. . . . . . . . . . . . . . . . . . . . . . 274</p> <p> 15.2 Code-Based Cryptography.. . . . . . . . . . . . . . . . . 279</p> <p> 15.3 Supersingular Isogeny Key Exchange.. . . . . . . . . . . . . 281</p> <p> 15.4 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 289</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 289</p> <p>Part IV Quantum Programming</p> <p>Chapter 16: Working with Q# 292</p> <p> 16.1 Basic Programming Concepts.. . . . . . . . . . . . . . . . 292</p> <p> 16.2 Getting Started with Q#.. . . . . . . . . . . . . . . . . . . 298</p> <p> 16.3 Grover’s Algorithm. . . . . . . . . . . . . . . . . . . . . 303</p> <p> 16.4 Deutsch-Jozsa Algorithm.. . . . . . . . . . . . . . . . . . 307</p> <p> 16.5 Bit Flipping.. . . . . . . . . . . . . . . . . . . . . . . . 310</p> <p> 16.6 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 311</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 311</p> <p>Chapter 17: Working with QASM 314</p> <p> 17.1 Basic Programming Concepts.. . . . . . . . . . . . . . . . 315</p> <p> 17.2 Getting Started with QASM.. . . . . . . . . . . . . . . . . 319</p> <p> 17.3 Quantum Error Correction. . . . . . . . . . . . . . . . . . 320</p> <p> 17.4 Grover’s Algorithm. . . . . . . . . . . . . . . . . . . . . 322</p> <p> 17.5 Deutsch-Jozsa Algorithm.. . . . . . . . . . . . . . . . . . 326</p> <p> 17.6 Summary.. . . . . . . . . . . . . . . . . . . . . . . . . 328</p> <p> Test Your Skills. . . . . . . . . . . . . . . . . . . . . . . 328</p> <p>Appendix: Answers to Test Your Skills Questions 330</p> <p>9780136793816, TOC, 5/7/2021</p>