Lecture Notes on Quantum Algorithms Andrew M.Childs Department of Computer Science, Institute for Advanced Computer Studies,and Joint Center for Quantum Information and Computer Science University of Maryland 19 September 2022
Lecture Notes on Quantum Algorithms Andrew M. Childs Department of Computer Science, Institute for Advanced Computer Studies, and Joint Center for Quantum Information and Computer Science University of Maryland 19 September 2022
Contents Preface vii 1 Preliminaries 1.1 Quantum data 1.2 Quantum circuits ..... 44 1.3 Universal gate sets 2 1.4 Reversible computation 2 1.5 Uniformity 44 1.6 Quantum complexity 44 3 l.7 Fault tolerance··.·········· 3 I Quantum circuits 2 Efficient universality of quantum circuits 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 Lemma2.3........·。。······ 9 3 Quantum circuit synthesis over Clifford+T 11 3.1 Converting to Matsumoto-Amano normal form.... 4.4 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 42 QFT over Z2n.···.··.·:·.····…·················· 17 4.3 Phase estimation.......·.·.· 19 4.4 QFT over ZN and over a general finite abelian group.····· 4 19 5 Discrete log and the hidden subgroup problem 21 21 5.2Dife-Hellman key exchange.·············· 1 5.3 The hidden subgroup problem..·.··...···. 22 5.4Shor's algorithm····················· 4.444 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.。.。·。·····。················ 7.2 Elliptic curve cryptography 3 7.3 Shor's algorithm for discrete log over elliptic curves 2 8 Quantum algorithms for number fields 33
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
今 Contents 25.5 leasuring an operator···· 126 26 Fast quantum simulation algorithms 129 26.1 No fast-.forwarding......·.·········· 4444。 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.·.·l53 30.2 The Jordan-Vigner 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
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