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.

Google Online Preview   Download