Transcription of Quantum Computing: Lecture Notes
1 Quantum Computing: Lecture NotesRonald de WolfQuSoft, CWI and University of [quant-ph] 11 Jan 2022 Dedicated to the memory of my fatherAbraham de Wolf (1942 2019)iiPreface from 2011 These Lecture Notes were formed in small chunks during my Quantum computing course at theUniversity of Amsterdam, Feb-May 2011, and compiled into one text thereafter. Each chapterwas covered in a Lecture of 2 45 minutes, with an additional 45-minute Lecture for exercises andhomework. The first half of the course (Chapters 1 7) covers Quantum algorithms, the second halfcovers Quantum complexity (Chapters 8 9), stuff involving Alice and Bob (Chapters 10 13), anderror-correction (Chapter 14). A 15th Lecture about physical implementations and general outlookwas more sketchy, and I didn t write Lecture Notes for chapters may also be read as a general introduction to the area of Quantum computationand information from the perspective of a theoretical computer scientist.
2 While I made an effortto make the text self-contained and consistent, it may still be somewhat rough around the edges; Ihope to continue polishing and adding to it. Comments & constructive criticism are very welcome,and can be sent who want to read more (much more.. ): see the book by Nielsen and Chuang [147] forthe general area, the book of John Watrous [180] for Quantum information theory, and the lecturenotes of John Preskill [149] for the theoretical physics , acknowledgments, subsequent updatesMost 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 [181], with a number of additions: the lower bound forSimon, the Fourier transform, the geometric explanation of Grover. Chapter 7 is newly written forthese Notes , inspired by Santha s survey [156].
3 Chapters 8 and 9 are largely new as well. Section 3of Chapter 8, and most of Chapter 10 are taken (with many changes) from my Quantum proofs survey paper with Andy Drucker [70]. Chapters 11 and 12 are partly taken from my non-localitysurvey with Harry Buhrman, Richard Cleve, and Serge Massar [46]. Chapters 13 and 14 are to Giannicola Scarpa (the teaching assistant for the first two editions of this course) foruseful comments on some of the 13: Updated and corrected a few things for the Feb-Mar 2013 version of this course, andincluded exercises for each chapter. Thanks to Harry Buhrman, Florian Speelman, and JeroenZuiddam for spotting some typos in the earlier 13: More updates, clarifications and corrections; moved some material from Chapter 2 to 1;changed and added some exercises.
4 Thanks to Jouke Witteveen for useful 14: Fixed and clarified a few more things. Thanks to Maarten Wegewijs for spotting a typoin Chapter 15: Updated a few small 15: Updated and corrected a few small things, added more exercises. Thanks to SrinivasanArunachalam, Carla Groenland, and Koen Groenland for useful 16: A few more corrections, thanks to Ralph Bottesch for useful 18: Many more corrections, more exercises, a new Chapter 6 about the Hidden SubgroupiiiProblem (the above-mentioned chapter numbers are for the earlier version of the Notes ), and movedthe hints about exercises to an Appendix for students who want to try the exercises first withouthints. Thanks to Joran van Apeldoorn, Srinivasan Arunachalam, Rens Baardman, Alexander Belov,Koen de Boer, Daniel Chernowitz, Andr as Gily en, Ronald de Haan, Leon Ingelse, Stacey Jeffery,Rafael Kiesel, Jens Klooster, Sam Kuypers, Christian Nesenberend, and Christian Schaffner foruseful 19: More corrections, clarifications and exercises, and new chapters about Hamiltoniansimulation (Chapter 9) and the HHL algorithm (Chapter 10).
5 These two chapters can be taughttogether in two lectures, with the longer Chapter 9 spilling over into the second Lecture if marked by (H) the exercises having a hint in Appendix C, and removed citations from exercises toprevent students looking up the original papers when doing the exercises (which is neither necessarynor helpful). Those references are [29, 66, 72, 42, 71, 82, 49, 23, 30, 21, 85, 57, 12]. Thanks toArjan Cornelissen, Sven Cornets de Groot, Gerrit Vos, and Harm de Vries for useful comments,and to Andr as Gily en for much help with Chapters 9 and 10. Thanks to my father and Mieke Beerfor hosting me for two months while I was recovering from an ankle fracture in a wheelchair, fromwhich much of these two chapters was 19: More corrections, clarifications and exercises.
6 Thanks to Joran van Apeldoorn, Andr asGily en, Stephanie Gonzalez, Sander Gribling, Jaco ter Hoeve, Arnold Kole, Lotte Mertens, StefanoPironio, Merel Schalkers, Jim Skulte, Iris Smit, Manuel Van, and Sebastian Zur for useful to Barbara Terhal for suggesting the possibility of dedicating these 21: More corrections, clarifications and exercises, and a new chapter about QMA and thelocal Hamiltonian problem (Chapter 13). Thanks to Dorit Aharonov, Tomas Ehrencron, Alex Grilo,Joris Kattem olle, Stan de Lange, Noah Linden, Tessel Majtlis, Nikhil Mande, Andrea Mazzocco,Robert Modderman, Thomas Preu, Philip Verduyn Lunel, Baer Ververgaert, and Carel Wagenaarfor useful 22: More corrections, clarifications and exercises. Thanks to Christiaan van Asperen,Yanlin Chen, Lynn Engelberts, Sevag Gharibian, Andr as Gily en, Diego Gonz alez-S anchez, BrunoJedynak, Joris Kattem olle, Julius Krebbekx, Zeph Landau, Noah Linden, Fr ed eric Magniez, RyanMann, and Yanelle Stolwijk for useful comments.
7 Ronald de Wolf, January 2022, AmsterdamivContents1 Quantum Introduction .. Quantum mechanics .. evolution .. Qubits and Quantum memory .. Elementary gates .. Example: Quantum teleportation ..92 The Circuit Model and the Deutsch-Jozsa Quantum computation .. circuits .. circuits .. Universality of various sets of elementary gates .. Quantum parallelism .. The early algorithms .. 193 Simon s The problem .. The Quantum algorithm .. Classical algorithms for Simon s problem .. bound .. bound .. 254 The Fourier The classical discrete Fourier transform .. The Fast Fourier Transform .. Application: multiplying two polynomials .. The Quantum Fourier transform.
8 An efficient Quantum circuit .. Application: phase estimation .. 33v5 Shor s Factoring Factoring .. Reduction from factoring to period-finding .. Shor s period-finding algorithm .. Continued fractions .. 416 Hidden Subgroup Hidden Subgroup Problem .. theory reminder .. and some instances of the HSP .. An efficient Quantum algorithm ifGis Abelian .. theory and the Quantum Fourier transform .. general algorithm for Abelian HSP .. General non-Abelian HSP .. symmetric group and the graph isomorphism problem .. QFT on coset states .. algorithm .. 517 Grover s Search The problem .. Grover s algorithm .. Amplitude amplification .. Application: satisfiability.
9 578 Quantum Walk Classical random walks .. Quantum walks .. Applications .. search .. problem .. a triangle in a graph .. 689 Hamiltonian Hamiltonians .. Method 1: Lie-Suzuki-Trotter methods .. Method 2: Linear combination of unitaries (LCU) .. simulation via LCU .. Method 3: Transforming block-encoded matrices .. simulation via transforming block-encoded matrices .. 7810 The HHL The linear-system problem .. The basic HHL algorithm for linear systems .. Improving the efficiency of the HHL agorithm .. 85vi11 Quantum Query Lower Introduction .. The polynomial method .. The Quantum adversary method .. 9012 Quantum Complexity Most functions need exponentially many gates.
10 Classical and Quantum complexity classes .. Classically simulating Quantum computers in polynomial space .. 9813 QMA and the Local Hamiltonian Quantum Merlin-Arthur (QMA) .. The local Hamiltonian problem .. Local Hamiltonian isQMA-complete .. Completeness and soundness .. Reducing the locality .. Other interesting problems inQMA.. Quantum interactive proofs .. 10814 Quantum Encodings, with a Non- Quantum Mixed states and general measurements .. Quantum encodings and their limits .. Lower bounds on locally decodable codes .. 11615 Quantum Communication Classical communication complexity .. The Quantum question .. Example 1: Distributed Deutsch-Jozsa .. Example 2: The Intersection problem.
