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 .. 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.

2 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 .. 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.

3 The standard method .. Query complexity of the HSP ..4511 Fourier analysis in nonabelian A brief introduction to representation theory .. Fourier analysis for nonabelian groups ..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.

4 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 ..89IV Quantum query complexity9120 Query complexity and the polynomial Quantum query complexity .. Quantum queries .. Quantum Algorithms and polynomials .. Symmetrization.

5 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 .. 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.

6 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 .. 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.

7 An adiabatic variant .. Locality .. 165 Bibliography167 PrefaceThis is a set of Lecture Notes on Quantum Algorithms . 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. Many of these Algorithms generalizethe main idea of Shor s algorithm .

8 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. We cover the two main methodsfor proving lower bounds on Quantum query complexity (the polynomial method and the adversarymethod), demonstrating limitations on the power of Quantum Algorithms . We also discuss how theconcept ofspan programsturns the Quantum adversary method into an upper bound, giving optimalquantum Algorithms for evaluating Boolean formulas.

9 In Part V, we describe Quantum Algorithms forsimulating the dynamics of Quantum systems. We alsodiscuss an application of Quantum simulation to an algorithm for linear systems. In Part VI, we discussadiabatic 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 onemight build a Quantum Notes were originally prepared for a course that was offered three times at the University ofWaterloo: in the winter terms of 2008 (as CO 781) and of 2011 and 2013 (as CO 781/CS 867/QIC 823). Ithank the students in the course for their feedback on the Lecture Notes . Each offering of the course covereda somewhat different set of topics. This document collects the material from all versions of the course andincludes a few subsequent material on Quantum Algorithms for algebraic problems has been collected into a review article thatwas written with Wim van Dam [34].

10 I thank Wim for his collaboration on that project, which stronglyinfluenced the presentation in Part 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 hope you find these Notes to be a useful resource for learning about Quantum 1 PreliminariesThis chapter briefly reviews some background material on Quantum computation. We cover these topics ata very high level, just to give a sense of what you should know to understand the rest of the Lecture any of these topics are unfamiliar, you can learn more about them from a text on Quantum computationsuch as Nielsen and Chuang [81]; Kitaev, Shen, and Vyalyi [64]; or Kaye, Laflamme, and Mosca [62]. Quantum dataA Quantum computer is a device that uses a Quantum mechanical representation of information to performcalculations.)