Lecture Notes on Quantum Algorithms

1 Lecture Notes onQuantum AlgorithmsAndrew M. ChildsDepartment of Computer Science,Institute for Advanced Computer Studies, andJoint Center for Quantum Information and Computer ScienceUniversity of Maryland29 April 2021iiContentsPrefacevii1 Quantum data .. Quantum circuits .. Universal gate sets .. Reversible computation .. Uniformity .. Quantum complexity .. Fault tolerance ..3I Quantum circuits52 Efficient universality of Quantum Subadditivity of errors .. The group commutator and a net around the identity .. Proof of the Solovay-Kitaev Theorem .. Proof of Lemma ..93 Quantum circuit synthesis over Clifford+ Converting to Matsumoto-Amano normal form.

2 Uniqueness of Matsumoto-Amano normal form .. Algebraic characterization of Clifford+Tunitaries .. From exact to approximate synthesis ..14II Quantum Algorithms for algebraic problems154 The abelian Quantum Fourier transform and phase Quantum Fourier transform .. QFT overZ2n.. Phase estimation .. QFT overZNand over a general finite abelian group ..195 Discrete log and the hidden subgroup Discrete log .. Diffie-Hellman key exchange .. The hidden subgroup problem .. Shor s algorithm ..236 The abelian HSP and decomposing abelian The abelian HSP .. Decomposing abelian groups ..277 Quantum attacks on elliptic curve Elliptic curves.

3 Elliptic curve cryptography .. Shor s algorithm for discrete log over elliptic curves ..328 Quantum Algorithms for number Review: Order finding .. Pell s equation .. Some basic algebraic number theory .. A periodic function for the units ofZ[ d] ..359 Period finding Period finding over the integers .. Period finding over the reals .. Other Algorithms for number fields ..4110 Quantum query complexity of the The nonabelian HSP and its applications .. The standard method .. Query complexity of the HSP ..4511 Fourier analysis in nonabelian A brief introduction to representation theory .. Fourier analysis for nonabelian groups.

4 4912 Fourier Weak Fourier sampling .. Normal subgroups .. Strong Fourier sampling ..5313 Kuperberg s algorithm for the dihedral The HSP in the dihedral group .. Fourier sampling in the dihedral group .. Combining states .. The Kuperberg sieve .. Analysis of the Kuperberg sieve .. Entangled measurements ..5814 The HSP in the Heisenberg The Heisenberg group .. Fourier sampling .. Two states are better than one ..6015 Approximating the Jones The Hadamard test .. The Jones polynomial .. Links from braids .. Representing braids in the Temperley-Lieb algebra .. A Quantum algorithm .. Quality of approximation .. Other Algorithms ..66 III Quantum walk6716 Continuous-time Quantum Continuous-time Quantum walk.

5 Random and Quantum walks on the hypercube .. Random and Quantum walks in one dimension .. Black-box traversal of the glued trees graph .. Quantum walk algorithm to traverse the glued trees graph .. Classical and Quantum mixing .. Classical lower bound ..7617 Discrete-time Quantum Discrete-time Quantum walk .. How to quantize a Markov chain .. Spectrum of the Quantum walk .. Hitting times ..8018 Unstructured Unstructured search .. Quantum walk algorithm .. Amplitude amplification and Quantum counting .. Search on graphs ..8519 Quantum walk Element distinctness .. Quantum walk algorithm .. Quantum walk search Algorithms with auxiliary data.

6 89IV Quantum query complexity9120 Query complexity and the polynomial Quantum query complexity .. Quantum queries .. Quantum Algorithms and polynomials .. Symmetrization .. Parity .. Unstructured search ..9621 The collision Problem statement .. Classical query complexity .. Quantum algorithm .. Toward a Quantum lower bound .. Constructing the functions .. Finishing the proof .. 10222 The Quantum adversary Quantum adversaries .. The adversary method .. Example: Unstructured search .. 10923 Span programs and formula The dual of the adversary method .. Span programs .. Unstructured search .. Formulas and games.

7 Function composition .. An algorithm from a dual adversary solution .. 11524 Learning Learning graphs and their complexity .. Unstructured search .. From learning graphs to span programs .. Element distinctness .. Other applications .. 120V Quantum simulation12125 Simulating Hamiltonian Hamiltonian dynamics .. Efficient simulation .. Product formulas .. Sparse Hamiltonians .. Measuring an operator .. 12626 Fast Quantum simulation No fast-forwarding .. Quantum walk .. Linear combinations of unitaries .. 13027 Quantum signal Block encoding .. Quantum signal processing .. Qubitization .. Application to Hamiltonian simulation.

8 137VI Adiabatic Quantum computing13928 The Quantum adiabatic Adiabatic evolution .. Proof of the adiabatic theorem .. 14229 Adiabatic An adiabatic optimization algorithm .. The running time and the gap .. Adabatic optimization algorithm for unstructured search .. 14930 An example of the success of adiabatic The ring of agrees .. The Jordan-Wigner transformation: From spins to fermions .. Diagonalizing a system of free fermions .. Diagonalizing the ring of agrees .. 15831 Universality of adiabatic Quantum The Feynman Quantum computer .. An adiabatic variant .. Locality .. 165 Bibliography167 PrefaceThis is a set of Lecture Notes on Quantum Algorithms .

9 It is primarily intended for graduate students who havealready taken an introductory course on Quantum information. Such a course typically covers only the earlybreakthroughs in Quantum Algorithms , namely Shor s factoring algorithm (1994) and Grover s searchingalgorithm (1996). Here we show that there is much more to Quantum computing by exploring some of themany Quantum Algorithms that have been developed over the past twenty-five Notes cover several major topics in Quantum Algorithms , divided into six parts: In Part I, we discussquantum circuits in particular, the problem of expressing a Quantum algorithmusing a given universal set of Quantum gates. In Part II, we discussquantum Algorithms for algebraic problems.

10 Many of these Algorithms generalizethe main idea of Shor s algorithm . These Algorithms use the Quantum Fourier transform and typicallyachieve an exponential (or at least superpolynomial) speedup over classical computers. In particular,we explore a group-theoretic problem called thehidden subgroup problem. A solution of this problemfor abelian groups leads to several applications; we also discuss what is known about the nonabeliancase. In Part III, we explore the concept ofquantum walk, a Quantum generalization of random walk. Thisconcept leads to a powerful framework for solving search problems, generalizing Grover s search algo-rithm. In Part IV, we discuss the model ofquantum query complexity.