Preface from 2011 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. 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 rdewolf at cwi. nl
Those who want to read more (much more. . . ): see the book by Nielsen and Chuang [117]. Attribution, acknowledgments, subsequent updates Most of the material in Chapters 1–6 [chapter numbers in this paragraph are for the 2011 version] comes from the first chapter of my PhD thesis [138], 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 [124]. 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 [57]. Chapters 11 and 12 are partly taken from my non-locality survey with Harry Buhrman, Richard Cleve, and Serge Massar [37]. Chapters 13 and 14 are new. Thanks to Giannicola Scarpa (the teaching assistant for the first two editions of this course) for useful comments on some of the chapters.
