This is a set of lecture notes on quantum algorithms. These notes were prepared for a course that was offered three times at the University of Waterloo (in 2008, 2011, and 2013), and that is currently being offered at the University of Maryland. 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 at least a few 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
- Quantum linear systems algorithm
### VI. Adiabatic quantum computing

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