Quantum Computing: Lecture Notes
[Pages:184]arXiv:1907.09415v2 [quant-ph] 20 Jan 2021
Quantum Computing: Lecture Notes
Ronald de Wolf
QuSoft, CWI and University of Amsterdam
Dedicated to the memory of my father Abraham de Wolf (1942?2019)
ii
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@cwi.nl
Those who want to read more (much more. . . ): see the book by Nielsen and Chuang [144] for the general area, the book of John Watrous [175] for quantum information theory, and the lecture notes of John Preskill [146] for the theoretical physics perspective.
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 [176], 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 [153]. 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 [70]. Chapters 11 and 12 are partly taken from my non-locality survey with Harry Buhrman, Richard Cleve, and Serge Massar [46]. 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.
Jan'13 : 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, and Jeroen Zuiddam for spotting some typos in the earlier version.
April'13 : More updates, clarifications and corrections; moved some material from Chapter 2 to 1; changed and added some exercises. Thanks to Jouke Witteveen for useful comments.
April'14 : Fixed and clarified a few more things. Thanks to Maarten Wegewijs for spotting a typo in Chapter 4.
March'15 : Updated a few small things.
July'15 : Updated and corrected a few small things, added more exercises. Thanks to Srinivasan Arunachalam, Carla Groenland, and Koen Groenland for useful comments.
May'16 : A few more corrections, thanks to Ralph Bottesch for useful comments.
Jan'18 : Many more corrections, more exercises, a new Chapter 6 about the Hidden Subgroup Prob-
iii
lem (the above-mentioned chapter numbers are for the earlier version of the notes), and moved the hints about exercises to an Appendix for students who want to try the exercises first without hints. 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 for useful comments. Jan'19 : More corrections and exercises, and new chapters about Hamiltonian simulation (Chapter 9) and the HHL algorithm (Chapter 10). These two chapters can be taught together in two lectures, with the longer Chapter 9 spilling over into the second lecture if necessary. I marked by `(H)' the exercises having a hint in Appendix C, and removed citations from exercises to prevent students looking up the original papers when doing the exercises (which is neither necessary nor helpful). Those references are [29, 66, 72, 42, 71, 82, 49, 23, 30, 21, 57, 12]. Thanks to Arjan 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 Beer for hosting me for two months while I was recovering from an ankle fracture in a wheelchair, from which much of these two chapters was written. July'19 : More corrections, clarifications and exercises. Thanks to Joran van Apeldoorn, Andr?as Gily?en, Stephanie Gonzalez, Sander Gribling, Jaco ter Hoeve, Arnold Kole, Lotte Mertens, Stefano Pironio, Merel Schalkers, Jim Skulte, Iris Smit, Manuel Van, and Sebastian Zur for useful comments. Thanks to Barbara Terhal for suggesting the possibility of dedicating these notes. January'21 : More corrections, clarifications and exercises, and a new chapter about QMA and the local Hamiltonian problem (Chapter 13). Thanks to Dorit Aharonov, Tomas Ehrencron, Alex Grilo, Joris Kattem?olle, Tessel Majtlis, Nikhil Mande, Andrea Mazzocco, Robert Modderman, Noah Linden, Thomas Preu, Stan de Lange, Noah Linden, Philip Verduyn Lunel, Baer Ververgaert, and Carel Wagenaar for useful comments.
? Ronald de Wolf, January 2021, Amsterdam iv
Contents
1 Quantum Computing
1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Unitary evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Qubits and quantum memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Elementary gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Example: quantum teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 The Circuit Model and Deutsch-Jozsa
13
2.1 Quantum computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Classical circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Universality of various sets of elementary gates . . . . . . . . . . . . . . . . . . . . . 15
2.3 Quantum parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 The early algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.2 Bernstein-Vazirani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Simon's Algorithm
21
3.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 The quantum algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Classical algorithms for Simon's problem . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.1 Upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.2 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 The Fourier Transform
27
4.1 The classical discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 The Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Application: multiplying two polynomials . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5 An efficient quantum circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.6 Application: phase estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
v
5 Shor's Factoring Algorithm
35
5.1 Factoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Reduction from factoring to period-finding . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3 Shor's period-finding algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.4 Continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6 Hidden Subgroup Problem
43
6.1 Hidden Subgroup Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.1.1 Group theory reminder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
6.1.2 Definition and some instances of the HSP . . . . . . . . . . . . . . . . . . . . 44
6.2 An efficient quantum algorithm if G is Abelian . . . . . . . . . . . . . . . . . . . . . 45
6.2.1 Representation theory and the quantum Fourier transform . . . . . . . . . . . 45
6.2.2 A general algorithm for Abelian HSP . . . . . . . . . . . . . . . . . . . . . . . 46
6.3 General non-Abelian HSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.3.1 The symmetric group and the graph isomorphism problem . . . . . . . . . . 48
6.3.2 Non-Abelian QFT on coset states . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.3.3 Query-efficient algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7 Grover's Search Algorithm
51
7.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.2 Grover's algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.3 Amplitude amplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
7.4 Application: satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
8 Quantum Walk Algorithms
59
8.1 Classical random walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
8.2 Quantum walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
8.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.3.1 Grover search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.3.2 Collision problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
8.3.3 Finding a triangle in a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
9 Hamiltonian Simulation
67
9.1 Hamiltonians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
9.2 Method 1: Lie-Suzuki-Trotter methods . . . . . . . . . . . . . . . . . . . . . . . . . . 68
9.3 Method 2: Linear combination of unitaries (LCU) . . . . . . . . . . . . . . . . . . . 69
9.3.1 Hamiltonian simulation via LCU . . . . . . . . . . . . . . . . . . . . . . . . . 71
9.4 Method 3: Transforming block-encoded matrices . . . . . . . . . . . . . . . . . . . . 72
9.4.1 Hamiltonian simulation via transforming block-encoded matrices . . . . . . . 74
10 The HHL Algorithm
77
10.1 The linear-system problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
10.2 The basic HHL algorithm for linear systems . . . . . . . . . . . . . . . . . . . . . . . 78
10.3 Improving the efficiency of the HHL agorithm . . . . . . . . . . . . . . . . . . . . . . 79
vi
11 Quantum Query Lower Bounds
81
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
11.2 The polynomial method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
11.3 The quantum adversary method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
12 Quantum Complexity Theory
89
12.1 Most functions need exponentially many gates . . . . . . . . . . . . . . . . . . . . . . 89
12.2 Classical and quantum complexity classes . . . . . . . . . . . . . . . . . . . . . . . . 90
12.3 Classically simulating quantum computers in polynomial space . . . . . . . . . . . . 92
13 QMA and the Local Hamiltonian Problem
95
13.1 Quantum Merlin-Arthur (QMA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
13.2 The local Hamiltonian problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
13.3 Local Hamiltonian is QMA-complete . . . . . . . . . . . . . . . . . . . . . . . . . . 98
13.3.1 Completeness and soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
13.3.2 Reducing the locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
13.4 Other interesting problems in QMA . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
13.5 Quantum interactive proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
14 Quantum Encodings, with a Non-Quantum Application
105
14.1 Mixed states and general measurements . . . . . . . . . . . . . . . . . . . . . . . . . 105
14.2 Quantum encodings and their limits . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
14.3 Lower bounds on locally decodable codes . . . . . . . . . . . . . . . . . . . . . . . . 108
15 Quantum Communication Complexity
113
15.1 Classical communication complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
15.2 The quantum question . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
15.3 Example 1: Distributed Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . . 115
15.4 Example 2: The Intersection problem . . . . . . . . . . . . . . . . . . . . . . . . . . 116
15.5 Example 3: The vector-in-subspace problem . . . . . . . . . . . . . . . . . . . . . . . 117
15.6 Example 4: Quantum fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
16 Entanglement and Non-Locality
123
16.1 Quantum non-locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
16.2 CHSH: Clauser-Horne-Shimony-Holt . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
16.3 Magic square game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
16.4 A non-local version of distributed Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . 128
17 Quantum Cryptography
131
17.1 Quantum key distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
17.2 Reduced density matrices and the Schmidt decomposition . . . . . . . . . . . . . . . 133
17.3 The impossibility of perfect bit commitment . . . . . . . . . . . . . . . . . . . . . . . 134
17.4 More quantum cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
vii
18 Error-Correction and Fault-Tolerance
139
18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
18.2 Classical error-correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
18.3 Quantum errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
18.4 Quantum error-correcting codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
18.5 Fault-tolerant quantum computation . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
18.6 Concatenated codes and the threshold theorem . . . . . . . . . . . . . . . . . . . . . 144
A Some Useful Linear Algebra
149
A.1 Vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
A.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
A.3 Inner product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
A.4 Unitary matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
A.5 Diagonalization and singular values . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
A.6 Tensor products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
A.7 Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
A.8 Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
A.9 The Pauli matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
A.10 Dirac notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
B Some other Useful Math and CS
155
B.1 Some notation, equalities and inequalities . . . . . . . . . . . . . . . . . . . . . . . . 155
B.2 Algorithms and probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
C Hints for Exercises
159
viii
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- journal of advocacy research and education 2015 vol 2
- internet virtual community a platform for learning online
- homepages for experts
- using technology to provide an interactive learning experience
- weidong cui curriculum vitae
- if you build it they will come implementing a marketing
- parallel image computation in clusters with task distributor
- alan turing and computation vuw
- encyclopedia of information systems
- quantum computing lecture notes
Related searches
- strategic management lecture notes pdf
- financial management lecture notes pdf
- business management lecture notes pdf
- organic chemistry lecture notes pdf
- corporate finance lecture notes pdf
- philosophy of education lecture notes slideshare
- business administration lecture notes pdf
- advanced microeconomics lecture notes pdf
- microeconomics lecture notes pdf
- marketing lecture notes pdf
- lecture notes in microeconomic theory
- mathematical logic lecture notes pdf