This is a set of lecture notes on quantum algorithms. These notes were prepared for a course that was offered at the University of Waterloo in 2008, 2011, and 2013, and at the University of Maryland in 2017. 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.

Part II of these notes has significant overlap with the review article *Quantum algorithms for algebraic problems* with Wim van Dam (arXiv:0812.0380, Reviews of Modern Physics **82**, 1–52 (2010)).

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 some mistakes. Corrections (by email to amchilds@umd.edu) are welcome.

- Preliminaries
### I. Quantum circuits

- Efficient universality of quantum circuits
- Quantum circuit synthesis over Clifford+
*T*### II. Quantum algorithms for algebraic problems

- The abelian quantum Fourier transform and phase estimation
- Discrete log and the hidden subgroup problem
- The abelian HSP and decomposing abelian groups
- Quantum attacks on elliptic curve cryptography
- Quantum algorithms for number fields
- Period finding from ℤ to ℝ
- Quantum query complexity of the HSP
- Fourier analysis in nonabelian groups
- Fourier sampling
- Kuperberg’s algorithm for the dihedral HSP
- The HSP in the Heisenberg group
- Approximating the Jones polynomial
### III. Quantum walk

- Continuous-time quantum walk
- Discrete-time quantum walk
- Unstructured search
- Quantum walk search
### IV. Quantum query complexity

- Query complexity and the polynomial method
- The collision problem
- The quantum adversary method
- Span programs and formula evaluation
- Learning graphs
### V. Quantum simulation

- Simulating Hamiltonian dynamics
- Fast quantum simulation algorithms
### VI. Adiabatic quantum computing

- The quantum adiabatic theorem
- Adiabatic optimization
- An example of the success of adiabatic optimization
- Universality of adiabatic quantum computation