《量子计算》课程教学资源（阅读文献）Lecture Notes on Quantum Algorithms（Andrew M. Childs）.pdf_大学文库

Contents Preface vii 1 Preliminaries 1 1.1 Quantum data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Universal gate sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Reversible computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.5 Uniformity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.6 Quantum complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.7 Fault tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 I Quantum circuits 5 2 Efficient universality of quantum circuits 7 2.1 Subadditivity of errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 The group commutator and a net around the identity . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Proof of the Solovay-Kitaev Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Proof of Lemma 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Quantum circuit synthesis over Clifford+T 11 3.1 Converting to Matsumoto-Amano normal form . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Uniqueness of Matsumoto-Amano normal form . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Algebraic characterization of Clifford+T unitaries . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 From exact to approximate synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II Quantum algorithms for algebraic problems 15 4 The abelian quantum Fourier transform and phase estimation 17 4.1 Quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 QFT over Z2n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.3 Phase estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.4 QFT over ZN and over a general finite abelian group . . . . . . . . . . . . . . . . . . . . . . . 19 5 Discrete log and the hidden subgroup problem 21 5.1 Discrete log . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Diffie-Hellman key exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.3 The hidden subgroup problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.4 Shor’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6 The abelian HSP and decomposing abelian groups 25 6.1 The abelian HSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.2 Decomposing abelian groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 7 Quantum attacks on elliptic curve cryptography 29 7.1 Elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.2 Elliptic curve cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 7.3 Shor’s algorithm for discrete log over elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . 32 8 Quantum algorithms for number fields 33

iv Contents 8.1 Review:Order finding······· 33 8.2 Pell's equation 33 8.3 Some basic algebraic number theory. 34 8.4 A periodic function for the units of Zvd 35 9 Period finding from Z to R 37 9.1 Period finding over the integers 37 9.2 Period finding over the reals.. 39 9.3 Other algorithms for number fields.. 41 10 Quantum query complexity of the HSP 43 10.1 The nonabelian HSP and its applications 4 43 10.2 The standard method. 44 l0.3 Query complexity of the HSP············ 45 11 Fourier analysis in nonabelian groups 47 ll.1 A brief introduction to representation theory·.·.·.·.··.·.·.····· 47 11.2 Fourier analysis for nonabelian groups 49 12 Fourier sampling 51 12.1 Weak Fourier sampling.··············· 12.2 Normal subgroups················· 52 12.3 Strong Fourier sampling.............. 53 13 Kuperberg's algorithm for the dihedral HSP 5 l3.1 The HSP in the dihedral group··. 55 l3.2 Fourier sampling in the dihedral group·.····· 56 l3.3 Combining states....·..·········· 5 l3.4 The Kuperberg sieve.········· 57 13.5 Analysis of the Kuperberg sieve..... 57 l3.6 Entangled measurements.······ 58 14 The HSP in the Heisenberg group 59 14.1 The Heisenberg group········ 59 14.2 Fourier sampling....··········· 4044444440 60 14.3 Two states are better than one.... 60 15 Approximating the Jones polynomial 6 15.1 The Hadamard test......·.·.·.· 63 15.2 The Jones polynomial. 4 15.3 Links from braids.. 64 15.4 Representing braids in the Temperley-Lieb algebra 64 15.5 A quantum algorithm················ 65 15.6 Quality of approximation 65 15.7 Other algorithms·..·· III Quantum walk 67 16 Continuous-time quantum walk 69 16.1 Continuous-.time quantum walk.············ 444 16.2 Random and quantum walks on the hypercube·....·....·.·.·.·.. 。。 70 16.3 Random and quantum walks in one dimension 71 l6.4 Black-box traversal of the glued trees graph............·.·.··..· 71 l6.5 Quantum walk algorithm to traverse the glued trees graph.:..··,.,.·.· 。。 16.6 Classical and quantum mixing.···························· 44 74 16.7 Classical lower bound 4 76 17 Discrete-time quantum walk 77 17.1 Discrete-time quantum walk... 77 17.2 How to quantize a Markov chain 4 78

iv Contents 8.1 Review: Order finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 8.2 Pell’s equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 8.3 Some basic algebraic number theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 8.4 A periodic function for the units of Z[ √ d] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 9 Period finding from Z to R 37 9.1 Period finding over the integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 9.2 Period finding over the reals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 9.3 Other algorithms for number fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 10 Quantum query complexity of the HSP 43 10.1 The nonabelian HSP and its applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 10.2 The standard method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 10.3 Query complexity of the HSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 11 Fourier analysis in nonabelian groups 47 11.1 A brief introduction to representation theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 11.2 Fourier analysis for nonabelian groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 12 Fourier sampling 51 12.1 Weak Fourier sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 12.2 Normal subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 12.3 Strong Fourier sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 13 Kuperberg’s algorithm for the dihedral HSP 55 13.1 The HSP in the dihedral group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 13.2 Fourier sampling in the dihedral group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 13.3 Combining states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 13.4 The Kuperberg sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 13.5 Analysis of the Kuperberg sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 13.6 Entangled measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 14 The HSP in the Heisenberg group 59 14.1 The Heisenberg group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 14.2 Fourier sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 14.3 Two states are better than one . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 15 Approximating the Jones polynomial 63 15.1 The Hadamard test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 15.2 The Jones polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 15.3 Links from braids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 15.4 Representing braids in the Temperley-Lieb algebra . . . . . . . . . . . . . . . . . . . . . . . . 64 15.5 A quantum algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 15.6 Quality of approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 15.7 Other algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 III Quantum walk 67 16 Continuous-time quantum walk 69 16.1 Continuous-time quantum walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 16.2 Random and quantum walks on the hypercube . . . . . . . . . . . . . . . . . . . . . . . . . . 70 16.3 Random and quantum walks in one dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 16.4 Black-box traversal of the glued trees graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 16.5 Quantum walk algorithm to traverse the glued trees graph . . . . . . . . . . . . . . . . . . . . 72 16.6 Classical and quantum mixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 16.7 Classical lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 17 Discrete-time quantum walk 77 17.1 Discrete-time quantum walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 17.2 How to quantize a Markov chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Contents 17.3 Spectrum of the quantum walk 79 17.4 Hitting times。.···.········· 80 18 Unstructured search 83 18.1 Unstructured search 4444 83 18.2 Quantum walk algorithm 。。 83 18.3 Amplitude amplification and quantum counting. 84 l8.4 Search on graphs·.。··.············ 85 19 Quantum walk search 87 19.1 Element distinctness............... 87 19.2 Quantum walk algorithm l9.3 Quantum walk search algorithms with auxiliary data·.··········· 89 IV Quantum query complexity 91 20 Query complexity and the polynomial method 93 20.1 Quantum query complexity 93 20.2 Quantum queries····.··· 94 20.3 Quantum algorithms and polynomials········· 94 20.4 Symmetrization.·....:.······· 95 20.5 Parity·········- 95 20.6 Unstructured search 。· 96 21 The collision problem 99 21.1 Problem statement . 99 2l.2 Classical query complexity.·· 99 21.3 Quantum algorithm 100 21.4 Toward a quantum lower bound.. 100 2l.5 Constructing the functions..·.·, 101 21.6 Finishing the proof.·.········· 102 22 The quantum adversary method 105 22.1 Quantum adversaries......... ....105 22.2 The adversary method...··........ 4444 106 22.3 Example:Unstructured search 109 23 Span programs and formula evaluation 111 23.1 The dual of the adversary method.....·· .....111 23.2 Span programs 112 23.3 Unstructured search··········· 113 23.4 Formulas and games············ 113 23.5 Function composition 4 114 23.6 An algorithm from a dual adversary solution 115 24 Learning graphs 117 24.1 Learning graphs and their complexity 。。 117 24.2 Unstructured search..................·。·..·.··· 117 24.3 From learning graphs to span programs······ 118 24.4 Element distinctness....。·。·.·····. 119 24.5 Other applications 120 Quantum simulation 121 25 Simulating Hamiltonian dynamics 123 25.1 Hamiltonian dynamics.······.· 123 25.2 Efficient simulation ... 123 25.3 Product formulas..... 4 124 25.4 Sparse Hamiltonians 125

Contents v 17.3 Spectrum of the quantum walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 17.4 Hitting times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 18 Unstructured search 83 18.1 Unstructured search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 18.2 Quantum walk algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 18.3 Amplitude amplification and quantum counting . . . . . . . . . . . . . . . . . . . . . . . . . . 84 18.4 Search on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 19 Quantum walk search 87 19.1 Element distinctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 19.2 Quantum walk algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 19.3 Quantum walk search algorithms with auxiliary data . . . . . . . . . . . . . . . . . . . . . . . 89 IV Quantum query complexity 91 20 Query complexity and the polynomial method 93 20.1 Quantum query complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 20.2 Quantum queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 20.3 Quantum algorithms and polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 20.4 Symmetrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 20.5 Parity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 20.6 Unstructured search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 21 The collision problem 99 21.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 21.2 Classical query complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 21.3 Quantum algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 21.4 Toward a quantum lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 21.5 Constructing the functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 21.6 Finishing the proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 22 The quantum adversary method 105 22.1 Quantum adversaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 22.2 The adversary method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 22.3 Example: Unstructured search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 23 Span programs and formula evaluation 111 23.1 The dual of the adversary method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 23.2 Span programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 23.3 Unstructured search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 23.4 Formulas and games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 23.5 Function composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 23.6 An algorithm from a dual adversary solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 24 Learning graphs 117 24.1 Learning graphs and their complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 24.2 Unstructured search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 24.3 From learning graphs to span programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 24.4 Element distinctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 24.5 Other applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 V Quantum simulation 121 25 Simulating Hamiltonian dynamics 123 25.1 Hamiltonian dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 25.2 Efficient simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 25.3 Product formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 25.4 Sparse Hamiltonians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

vi Contents 25.5 Measuring an operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 26 Fast quantum simulation algorithms 129 26.1 No fast-forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 26.2 Quantum walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 26.3 Linear combinations of unitaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 27 Quantum signal processing 133 27.1 Block encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 27.2 Quantum signal processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 27.3 Qubitization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 27.4 Application to Hamiltonian simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 VI Adiabatic quantum computing 139 28 The quantum adiabatic theorem 141 28.1 Adiabatic evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 28.2 Proof of the adiabatic theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 29 Adiabatic optimization 147 29.1 An adiabatic optimization algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 29.2 The running time and the gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 29.3 Adabatic optimization algorithm for unstructured search . . . . . . . . . . . . . . . . . . . . . 149 30 An example of the success of adiabatic optimization 153 30.1 The ring of agrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 30.2 The Jordan-Wigner transformation: From spins to fermions . . . . . . . . . . . . . . . . . . . 154 30.3 Diagonalizing a system of free fermions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 30.4 Diagonalizing the ring of agrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 31 Universality of adiabatic quantum computation 161 31.1 The Feynman quantum computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 31.2 An adiabatic variant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 31.3 Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 Bibliography 167

Preface This is a set of lecture notes on quantum algorithms.It is primarily intended for graduate students who have already taken an introductory course on quantum information.Such a course typically covers only the early breakthroughs in quantum algorithms,namely Shor's factoring algorithm (1994)and Grover's searching algorithm(1996).Here we show that there is much more to quantum computing by exploring some of the many quantum algorithms that have been developed over the past twenty-five years. These notes cover several major topics in quantum algorithms.divided into six parts: In Part I,we discuss quantum circuits-in particular,the problem of expressing a quantum algorithm using a given universal set of quantum gates. In Part II,we discuss quantum algorithms for algebraic problems.Many of these algorithms generalize the main idea of Shor's algorithm.These algorithms use the quantum Fourier transform and typically achieve an exponential (or at least superpolynomial)speedup over classical computers.In particular, we explore a group-theoretic problem called the hidden subgroup problem.A solution of this problem for abelian groups leads to several applications;we also discuss what is known about the nonabelian case. In Part III,we explore the concept of quantum walk,a quantum generalization of random walk.This concept leads to a powerful framework for solving search problems,generalizing Grover's search algo- rithm. In Part IV,we discuss the model of quantum query complerity.We cover the two main methods for proving lower bounds on quantum query complexity(the polynomial method and the adversary method),demonstrating limitations on the power of quantum algorithms.We also discuss how the concept of span programs turns the quantum adversary method into an upper bound,giving optimal quantum algorithms for evaluating Boolean formulas. In Part V,we describe quantum algorithms for simulating the dynamics of quantum systems.We also discuss an application of quantum simulation to an algorithm for linear systems. In Part VI,we discuss adiabatic quantum computing,a general approach to solving optimization prob- lems(in a similar spirit to simulated annealing).Related ideas may also provide insights into how one might build a quantum computer. These notes were originally prepared for a course that was offered three times at the University of Waterloo:in the winter terms of 2008 (as CO 781)and of 2011 and 2013 (as CO 781/CS 867/QIC 823).I thank the students in the course for their feedback on the lecture notes.Each offering of the course covered a somewhat different set of topics.This document collects the material from all versions of the course and includes a few subsequent improvements. The material on quantum algorithms for algebraic problems has been collected into a review article that was written with Wim van Dam [34].I thank Wim for his collaboration on that project,which strongly infuenced the presentation in Part II Please keep in mind that these are rough lecture notes;they are not meant to be a comprehensive treat- ment of the subject,and there are surely at least a few mistakes.Corrections(by email to amchilds@umd.edu) are welcome. I hope you find these notes to be a useful resource for learning about quantum algorithms

Preface This is a set of lecture notes on quantum algorithms. It is primarily intended for graduate students who have already taken an introductory course on quantum information. Such a course typically covers only the early breakthroughs in quantum algorithms, namely Shor’s factoring algorithm (1994) and Grover’s searching algorithm (1996). Here we show that there is much more to quantum computing by exploring some of the many quantum algorithms that have been developed over the past twenty-five years. These notes cover several major topics in quantum algorithms, divided into six parts: • In Part I, we discuss quantum circuits—in particular, the problem of expressing a quantum algorithm using a given universal set of quantum gates. • In Part II, we discuss quantum algorithms for algebraic problems. Many of these algorithms generalize the main idea of Shor’s algorithm. These algorithms use the quantum Fourier transform and typically achieve an exponential (or at least superpolynomial) speedup over classical computers. In particular, we explore a group-theoretic problem called the hidden subgroup problem. A solution of this problem for abelian groups leads to several applications; we also discuss what is known about the nonabelian case. • In Part III, we explore the concept of quantum walk, a quantum generalization of random walk. This concept leads to a powerful framework for solving search problems, generalizing Grover’s search algorithm. • In Part IV, we discuss the model of quantum query complexity. We cover the two main methods for proving lower bounds on quantum query complexity (the polynomial method and the adversary method), demonstrating limitations on the power of quantum algorithms. We also discuss how the concept of span programs turns the quantum adversary method into an upper bound, giving optimal quantum algorithms for evaluating Boolean formulas. • In Part V, we describe quantum algorithms for simulating the dynamics of quantum systems. We also discuss an application of quantum simulation to an algorithm for linear systems. • In Part VI, we discuss adiabatic quantum computing, a general approach to solving optimization problems (in a similar spirit to simulated annealing). Related ideas may also provide insights into how one might build a quantum computer. These notes were originally prepared for a course that was offered three times at the University of Waterloo: in the winter terms of 2008 (as CO 781) and of 2011 and 2013 (as CO 781/CS 867/QIC 823). I thank the students in the course for their feedback on the lecture notes. Each offering of the course covered a somewhat different set of topics. This document collects the material from all versions of the course and includes a few subsequent improvements. The material on quantum algorithms for algebraic problems has been collected into a review article that was written with Wim van Dam [34]. I thank Wim for his collaboration on that project, which strongly influenced the presentation in Part II. Please keep in mind that these are rough lecture notes; they are not meant to be a comprehensive treatment of the subject, and there are surely at least a few mistakes. Corrections (by email to amchilds@umd.edu) are welcome. I hope you find these notes to be a useful resource for learning about quantum algorithms

Chapter 1 Preliminaries This chapter briefly reviews some background material on quantum computation.We cover these topics at a very high level,just to give a sense of what you should know to understand the rest of the lecture notes. If any of these topics are unfamiliar,you can learn more about them from a text on quantum computation such as Nielsen and Chuang [81];Kitaev,Shen,and Vyalyi [64];or Kaye,Laflamme,and Mosca [62]. 1.1 Quantum data A quantum computer is a device that uses a quantum mechanical representation of information to perform calculations.Information is stored in quantum bits,the states of which can be represented as e2-normalized vectors in a complex vector space.For example,we can write the state of n qubits as ）=】 azlz) (1.1) x∈{0,1}m where the arEC satisfy a2=1.We refer to the basis of states r)as the computational basis. It will often be useful to think of quantum states as storing data in a more abstract form.For example, given a group G,we could write g)for a basis state corresponding to the group element gEG,and l)=∑bglg) (1.2) 9EG for an arbitrary superposition over the group.We assume that there is some canonical way of efficiently representing group elements using bit strings;it is usually unnecessary to make this representation explicit. If a quantum computer stores the state and the state o),its overall state is given by the tensor product of those two states.This may be denoted ))=)o)=l,). 1.2 Quantum circuits The allowed operations on(pure)quantum states are those that map normalized states to normalized states, namely unitary operators U,satisfying UUt=UiU=I.(You probably know that there are more general quantum operations,but for the most part we will not need to use them in this course.) To have a sensible notion of efficient computation,we require that the unitary operators appearing in a quantum computation are realized by quantum circuits.We are given a set of gates,each of which acts on one or two qubits at a time (meaning that it is a tensor product of a one-or two-qubit operator with the identity operator on the remaining qubits).A quantum computation begins in the 0)state,applies a sequence of one-and two-qubit gates chosen from the set of allowed gates,and finally reports an outcome obtained by measuring in the computational basis

Chapter 1 Preliminaries This chapter briefly reviews some background material on quantum computation. We cover these topics at a very high level, just to give a sense of what you should know to understand the rest of the lecture notes. If any of these topics are unfamiliar, you can learn more about them from a text on quantum computation such as Nielsen and Chuang [81]; Kitaev, Shen, and Vyalyi [64]; or Kaye, Laflamme, and Mosca [62]. 1.1 Quantum data A quantum computer is a device that uses a quantum mechanical representation of information to perform calculations. Information is stored in quantum bits, the states of which can be represented as `2-normalized vectors in a complex vector space. For example, we can write the state of n qubits as |ψi = X x∈{0,1}n ax|xi (1.1) where the ax ∈ C satisfy P x |ax| 2 = 1. We refer to the basis of states |xi as the computational basis. It will often be useful to think of quantum states as storing data in a more abstract form. For example, given a group G, we could write |gi for a basis state corresponding to the group element g ∈ G, and |φi = X g∈G bg|gi (1.2) for an arbitrary superposition over the group. We assume that there is some canonical way of efficiently representing group elements using bit strings; it is usually unnecessary to make this representation explicit. If a quantum computer stores the state |ψi and the state |φi, its overall state is given by the tensor product of those two states. This may be denoted |ψi ⊗ |φi = |ψi|φi = |ψ, φi. 1.2 Quantum circuits The allowed operations on (pure) quantum states are those that map normalized states to normalized states, namely unitary operators U, satisfying UU† = U †U = I. (You probably know that there are more general quantum operations, but for the most part we will not need to use them in this course.) To have a sensible notion of efficient computation, we require that the unitary operators appearing in a quantum computation are realized by quantum circuits. We are given a set of gates, each of which acts on one or two qubits at a time (meaning that it is a tensor product of a one- or two-qubit operator with the identity operator on the remaining qubits). A quantum computation begins in the |0i state, applies a sequence of one- and two-qubit gates chosen from the set of allowed gates, and finally reports an outcome obtained by measuring in the computational basis

Chapter 1.Preliminaries 1.3 Universal gate sets In principle,any unitary operator on n qubits can be implemented using only 1-and 2-qubit gates.Thus we say that the set of all 1-and 2-qubit gates is (eractly)universal.Of course,some unitary operators may take many more 1-and 2-qubit gates to realize than others,and indeed,a counting argument shows that most unitary operators on n qubits can only be realized using an exponentially large circuit of 1-and 2-qubit gates. In general,we are content to give circuits that give good approximations of our desired unitary transfor- mations.We say that a circuit with gates U1,U2,...,U approximates U with precision e if IU-U..U2U1l≤e. (1.3) Here denotes some appropriate matrix norm,which should have the property that ifU-Vl is small, then U should be hard to distinguish from V no matter what quantum state they act on.A natural choice (which will be suitable for our purposes)is the spectral norm A‖：=max IA )川 (1.4) (where=v(l)denotes the vector 2-norm of )i.e.,the largest singular value of A.Then we call a set of elementary gates universal if any unitary operator on a fixed number of qubits can be approximated to any desired precision e using elementary gates. It turns out that there are finite sets of gates that are universal:for example,the set [H,T,C}with /1 000 ei/8 0 0 1 T:= 0 0 H 0 e-ir/ 0 001 (1.5) 0 010 There are situations in which we say a set of gates is effectively universal,even though it cannot actually approximate any unitary operator on n qubits.For example,the set {H,T2,Tof},where /1 0000000 01000000 00100000 Tof : 00010000 00001000 (1.6) 0000010 0 0 000000 1 0 0000010 is universal,but only if we allow the use of ancilla qubits (qubits that start and end in the 0)state). Similarly,the basis {H,Tof}is universal in the sense that,with ancillas,it can approximate any orthogonal matrix.It clearly cannot approximate complex unitary matrices,since the entries of H and Tof are real; but the effect of arbitrary unitary transformations can be simulated using orthogonal ones by simulating the real and imaginary parts separately. 1.4 Reversible computation Unitary matrices are invertible:in particular,U-1=Ut.Thus any unitary transformation is a reversible operation.This may seem at odds with how we often define classical circuits,using irreversible gates such as AND and OR.But in fact,any classical computation can be made reversible by replacing any irreversible gate zg(x)by the reversible gate (x,y)(,yg(x)),and running it on the input (x,0),producing (r,g()).In other words,by storing all intermediate steps of the computation,we make it reversible. On a quantum computer,storing all intermediate computational steps could present a problem,since two identical results obtained in different ways would not be able to interfere.However,there is an easy way to

2 Chapter 1. Preliminaries 1.3 Universal gate sets In principle, any unitary operator on n qubits can be implemented using only 1- and 2-qubit gates. Thus we say that the set of all 1- and 2-qubit gates is (exactly) universal. Of course, some unitary operators may take many more 1- and 2-qubit gates to realize than others, and indeed, a counting argument shows that most unitary operators on n qubits can only be realized using an exponentially large circuit of 1- and 2-qubit gates. In general, we are content to give circuits that give good approximations of our desired unitary transformations. We say that a circuit with gates U1, U2, . . . , Ut approximates U with precision if kU − Ut . . . U2U1k ≤ . (1.3) Here k·k denotes some appropriate matrix norm, which should have the property that if kU − V k is small, then U should be hard to distinguish from V no matter what quantum state they act on. A natural choice (which will be suitable for our purposes) is the spectral norm kAk := max |ψi kA|ψik k|ψik , (1.4) (where k|ψik = p hψ|ψi denotes the vector 2-norm of |ψi), i.e., the largest singular value of A. Then we call a set of elementary gates universal if any unitary operator on a fixed number of qubits can be approximated to any desired precision using elementary gates. It turns out that there are finite sets of gates that are universal: for example, the set {H, T, C} with H := 1 √ 2 1 1 1 −1 T := e iπ/8 0 0 e −iπ/8 C :=   1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0   . (1.5) There are situations in which we say a set of gates is effectively universal, even though it cannot actually approximate any unitary operator on n qubits. For example, the set {H, T2 , Tof}, where Tof :=   1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0   (1.6) is universal, but only if we allow the use of ancilla qubits (qubits that start and end in the |0i state). Similarly, the basis {H, Tof} is universal in the sense that, with ancillas, it can approximate any orthogonal matrix. It clearly cannot approximate complex unitary matrices, since the entries of H and Tof are real; but the effect of arbitrary unitary transformations can be simulated using orthogonal ones by simulating the real and imaginary parts separately. 1.4 Reversible computation Unitary matrices are invertible: in particular, U −1 = U † . Thus any unitary transformation is a reversible operation. This may seem at odds with how we often define classical circuits, using irreversible gates such as and and or. But in fact, any classical computation can be made reversible by replacing any irreversible gate x 7→ g(x) by the reversible gate (x, y) 7→ (x, y ⊕ g(x)), and running it on the input (x, 0), producing (x, g(x)). In other words, by storing all intermediate steps of the computation, we make it reversible. On a quantum computer, storing all intermediate computational steps could present a problem, since two identical results obtained in different ways would not be able to interfere. However, there is an easy way to

1.5.Uniformity 3 remove the accumulated information.After performing the classical computation with reversible gates,we simply XoR the answer into an ancilla register,and then perform the computation in reverse.Thus we can implement the map (x,y)(z,y f(z))even when f is a complicated circuit consisting of many gates. Using this trick,any computation that can be performed efficiently on a classical computer can be performed efficiently on a quantum computer:if we can efficiently implement the map xf(z)on a classical computer,we can efficiently perform the transformation y),yf(z))on a quantum computer.This transformation can be applied to any superposition of computational basis states,so for example,we can perform the transformation 1 ∑k,0→∑k,fa》 V2m (1.7） x∈{0,1} x∈{0,1}n Note that this does not necessarily mean we can efficiently implement the map )f(z)),even when f is a bijection(so that this is indeed a unitary transformation).However,if we can efficiently invert f,then we can indeed do this efficiently by computing f(z)in another register and then reversibly uncomputing x using the inverse of the reversible circuit for computing f-1 1.5 Uniformity When we give an algorithm for a computational problem,we consider inputs of varying sizes.Typically, the circuits for instances of different sizes will be related to one another in a simple way.But this need not be the case;and indeed,given the ability to choose an arbitrary circuit for each input size,we could have circuits computing uncomputable languages.Thus we require that our circuits be uniformly generated:say, that there exists a fixed(classical)Turing machine that,given a tape containing the symbol'1'n times, outputs a description of the nth circuit in time poly(n). 1.6 Quantum complexity We say that an algorithm for a problem is efficient if the circuit describing it contains a number of gates that is polynomial in the number of bits needed to write down the input.For example,if the input is a number modulo N,the input size is [log2 N]. With a quantum computer,as with a randomized (or noisy)classical computer,the final result of a computation may not be correct with certainty.Instead,we are typically content with an algorithm that can produce the correct answer with high enough probability (for a decision problem,bounded above 1/2; for a non-decision problem for which we can check a correct solution,(1)).By repeating the computation many times,we can make the probability of outputting an incorrect answer arbitrarily small. In addition to considering explicit computational problems,in which the input is a string,we will also consider the concept of query complerity.Here the input is a black box transformation,and our goal is to discover some property of the transformation by making as few queries as possible.For example,in Simon's problem,we are given a transformation f:Z2S satisfying f(r)=f(y)iff y=xt for some unknown tEZ2,and the goal is to learn t.The main advantage of considering query complexity is that it allows us to prove lower bounds on the number of queries required to solve a given problem.Furthermore,if we find an efficient algorithm for a problem in query complexity,then if we are given an explicit circuit realizing the black-box transformation,we will have an efficient algorithm for an explicit computational problem. Sometimes,we care not just about the size of a circuit for implementing a particular unitary operation, but also about its depth,the maximum number of gates on any path from an input to an output.The depth of a circuit tells us how long it takes to implement if we can perform gates in parallel. 1.7 Fault tolerance In any real computer,operations cannot be performed perfectly.Quantum gates and measurements may be performed imprecisely,and errors may happen even to stored data that is not being manipulated.Fortu-

1.5. Uniformity 3 remove the accumulated information. After performing the classical computation with reversible gates, we simply xor the answer into an ancilla register, and then perform the computation in reverse. Thus we can implement the map (x, y) 7→ (x, y ⊕ f(x)) even when f is a complicated circuit consisting of many gates. Using this trick, any computation that can be performed efficiently on a classical computer can be performed efficiently on a quantum computer: if we can efficiently implement the map x 7→ f(x) on a classical computer, we can efficiently perform the transformation |x, yi 7→ |x, y ⊕f(x)i on a quantum computer. This transformation can be applied to any superposition of computational basis states, so for example, we can perform the transformation 1 √ 2 n X x∈{0,1}n |x, 0i 7→ 1 √ 2 n X x∈{0,1}n |x, f(x)i. (1.7) Note that this does not necessarily mean we can efficiently implement the map |xi 7→ |f(x)i, even when f is a bijection (so that this is indeed a unitary transformation). However, if we can efficiently invert f, then we can indeed do this efficiently by computing f(x) in another register and then reversibly uncomputing x using the inverse of the reversible circuit for computing f −1 . 1.5 Uniformity When we give an algorithm for a computational problem, we consider inputs of varying sizes. Typically, the circuits for instances of different sizes will be related to one another in a simple way. But this need not be the case; and indeed, given the ability to choose an arbitrary circuit for each input size, we could have circuits computing uncomputable languages. Thus we require that our circuits be uniformly generated: say, that there exists a fixed (classical) Turing machine that, given a tape containing the symbol ‘1’ n times, outputs a description of the nth circuit in time poly(n). 1.6 Quantum complexity We say that an algorithm for a problem is efficient if the circuit describing it contains a number of gates that is polynomial in the number of bits needed to write down the input. For example, if the input is a number modulo N, the input size is dlog2 Ne. With a quantum computer, as with a randomized (or noisy) classical computer, the final result of a computation may not be correct with certainty. Instead, we are typically content with an algorithm that can produce the correct answer with high enough probability (for a decision problem, bounded above 1/2; for a non-decision problem for which we can check a correct solution, Ω(1)). By repeating the computation many times, we can make the probability of outputting an incorrect answer arbitrarily small. In addition to considering explicit computational problems, in which the input is a string, we will also consider the concept of query complexity. Here the input is a black box transformation, and our goal is to discover some property of the transformation by making as few queries as possible. For example, in Simon’s problem, we are given a transformation f : Z n 2 → S satisfying f(x) = f(y) iff y = x ⊕ t for some unknown t ∈ Z n 2 , and the goal is to learn t. The main advantage of considering query complexity is that it allows us to prove lower bounds on the number of queries required to solve a given problem. Furthermore, if we find an efficient algorithm for a problem in query complexity, then if we are given an explicit circuit realizing the black-box transformation, we will have an efficient algorithm for an explicit computational problem. Sometimes, we care not just about the size of a circuit for implementing a particular unitary operation, but also about its depth, the maximum number of gates on any path from an input to an output. The depth of a circuit tells us how long it takes to implement if we can perform gates in parallel. 1.7 Fault tolerance In any real computer, operations cannot be performed perfectly. Quantum gates and measurements may be performed imprecisely, and errors may happen even to stored data that is not being manipulated. Fortu-