Quantum Computing: Lecture Notes

1 Quantum computing : Lecture Notes Ronald de Wolf Preface These Lecture Notes were formed in small chunks during my Quantum computing course at the University of Amsterdam, Feb-May 2011, and compiled into one text thereafter. Each chapter was covered in a Lecture of 2 45 minutes, with an additional 45-minute Lecture for exercises and homework. The first half of the course (Chapters 1 7) covers Quantum algorithms, the second half covers Quantum complexity (Chapters 8 9), stuff involving Alice and Bob (Chapters 10 13), and error-correction (Chapter 14). A 15th Lecture about physical implementations and general outlook was more sketchy, and I didn't write Lecture Notes for it.

2 These chapters may also be read as a general introduction to the area of Quantum computation and information from the perspective of a theoretical computer scientist. While I made an effort to make the text self-contained and consistent, it may still be somewhat rough around the edges; I. hope to continue polishing and adding to it. Comments & constructive criticism are very welcome, and can be sent to Attribution and acknowledgements Most of the material in Chapters 1 6 comes from the first chapter of my PhD thesis [71], with a number of additions: the lower bound for Simon, the Fourier transform, the geometric explanation of Grover.

3 Chapter 7 is newly written for these Notes , inspired by Santha's survey [62]. Chapters 8. and 9 are largely new as well. Section 3 of Chapter 8, and most of Chapter 10 are taken (with many changes) from my Quantum proofs survey paper with Andy Drucker [28]. Chapters 11. and 12 are partly taken from my non-locality survey with Harry Buhrman, Richard Cleve, and Serge Massar [17]. Chapters 13 and 14 are new. Thanks to Giannicola Scarpa for useful comments on some of the chapters. Version 2 (Jan'12): updated and corrected a few things for the Feb-Mar 2013 version of this course, and included exercises for each chapter.

4 Thanks to Harry Buhrman, Florian Speelman, Jeroen Zuiddam for spotting some typos in the earlier version. Ronald de Wolf January 2012, Amsterdam i Contents 1 Quantum computing 1. Introduction .. 1. Quantum mechanics .. 2. Superposition .. 2. Measurement .. 3. Unitary evolution .. 4. Quantum memory .. 5. 2 The Circuit Model and Deutsch-Jozsa 7. Quantum computation .. 7. Classical circuits .. 7. Quantum circuits .. 8. Example: Quantum teleportation and no-cloning .. 9. Universality of various sets of elementary gates .. 10. Quantum parallelism .. 10. The early algorithms.

5 11. Deutsch-Jozsa .. 12. Bernstein-Vazirani .. 13. 3 Simon's algorithm 15. The problem .. 15. The Quantum algorithm .. 15. Classical lower bound for Simon's problem .. 16. 4 The Fourier Transform 19. The classical discrete Fourier transform .. 19. The Fast Fourier Transform .. 20. Application: multiplying two polynomials .. 20. The Quantum Fourier transform .. 21. An efficient Quantum circuit .. 22. Application: phase estimation .. 23. 5 Shor's Factoring algorithm 25. Factoring .. 25. Reduction from factoring to period-finding .. 25. ii Shor's period-finding algorithm .

6 27. Continued fractions .. 29. 6 Grover's Search algorithm 32. The problem .. 32. Grover's algorithm .. 32. Amplitude amplification .. 35. Application: satisfiability .. 35. 7 Quantum Random Walks Algorithms 38. Classical random walks .. 38. Quantum random walks .. 39. Applications .. 41. Grover search .. 42. Collision problem .. 42. Finding a triangle in a graph .. 43. 8 Quantum Query Lower Bounds 46. Introduction .. 46. The polynomial method .. 47. The Quantum adversary method .. 49. 9 Quantum Complexity Theory 52. Most functions need exponentially many gates.

7 52. Classical and Quantum complexity classes .. 53. Classically simulating Quantum computers in polynomial space .. 54. 10 Quantum Encodings, with a Non- Quantum Application 57. Mixed states and general measurements .. 57. Quantum encodings and their limits .. 58. Lower bounds on locally decodable codes .. 60. 11 Quantum Communication Complexity 63. Classical communication complexity .. 63. The Quantum question .. 64. Example 1: Distributed Deutsch-Jozsa .. 65. Example 2: The Intersection problem .. 66. Example 3: The vector-in-subspace problem .. 67. Simultaneous communication: Quantum fingerprinting.

8 67. 12 Entanglement and Non-locality 70. Quantum non-locality .. 70. CHSH: Clauser-Horne-Shimony-Holt .. 72. Magic square game .. 73. A non-local version of distributed Deutsch-Jozsa .. 75. iii 13 Quantum Cryptography 77. Quantum key distribution .. 77. Reduced density matrices and the Schmidt decomposition .. 79. The impossibility of perfect bit commitment .. 80. More Quantum cryptography .. 81. 14 Error-Correction and Fault-Tolerance 83. Introduction .. 83. Classical error-correction .. 83. Quantum errors .. 84. Quantum error-correcting codes .. 85. Fault-tolerant Quantum computation.

9 87. Concatenated codes and the threshold theorem .. 88. A Some Useful Linear Algebra 90. Some Terminology and Notation .. 90. Unitary Matrices .. 90. Diagonalization and Singular Values .. 91. Trace .. 92. Tensor Products .. 92. Rank .. 93. Dirac Notation .. 93. B Some other Useful Math 94. iv Chapter 1. Quantum computing Introduction Today's computers both in theory (Turing machines) and practice (PCs) are based on classical physics. However, modern Quantum physics tells us that the world behaves quite differently. A. Quantum system can be in a superposition of many different states at the same time, and can exhibit interference effects during the course of its evolution.

10 Moreover, spatially separated Quantum systems may be entangled with each other and operations may have non-local effects because of this. Quantum computation is the field that investigates the computational power and other prop- erties of computers based on Quantum -mechanical principles. An important objective is to find Quantum algorithms that are significantly faster than any classical algorithm solving the same problem. The field started in the early 1980s with suggestions for analog Quantum computers by Paul Benioff [11] and Richard Feynman [31, 32], and reached more digital ground when in 1985.