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. 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.

2 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. 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].

3 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. 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.

4 The early algorithms .. 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 .. 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.

5 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 .. 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.

6 65. Example 2: The Intersection problem .. 66. Example 3: The vector-in-subspace problem .. 67. Simultaneous communication: Quantum fingerprinting .. 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 .. 87. Concatenated codes and the threshold theorem.

7 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. 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.

8 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. David Deutsch defined the universal Quantum Turing machine [25]. The following years saw only sparse activity, notably the development of the first algorithms by Deutsch and Jozsa [27] and by Simon [65], and the development of Quantum complexity theory by Bernstein and Vazirani [14]. However, interest in the field increased tremendously after Peter Shor's very surprising discovery of efficient Quantum algorithms for the problems of integer factorization and discrete logarithms in 1994 [64].

9 Since most of current classical cryptography is based on the assumption that these two problems are computationally hard, the ability to actually build and use a Quantum computer would allow us to break most current classical cryptographic systems, notably the RSA system [60, 61]. (In contrast, a Quantum form of cryptography due to Bennett and Brassard [13] is unbreakable even for Quantum computers.). Let us mention three different motivations for studying Quantum computers, from practical to more philosophical: 1. The process of miniaturization that has made current classical computers so powerful and cheap, has already reached micro-levels where Quantum effects occur. Chip-makers tend to go to great lengths to suppress those Quantum effects, but instead one might also try to make good use of them.

10 2. Making use of Quantum effects allows one to speed-up certain computations enormously (sometimes exponentially), and even enables some things that are impossible for classical 1. computers The main purpose of this course is to explain these things (algorithms, crypto, etc.) in detail. 3. Finally, one might state the main goal of theoretical computer science as study the power and limitations of the strongest-possible computational devices that nature allows us. Since our current understanding of nature is Quantum mechanical, theoretical computer science should be studying the power of Quantum computers, not classical ones. Before limiting ourselves to theory, let us say a few words about practice: to what extent will Quantum computers ever be built? At this point in time, it is just too early to tell.