Lecture Notes on Quantum Algorithms

Andrew Childs

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 and 2021. 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 some further 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.

Contents

  1. Preliminaries

    I. Quantum circuits

  2. Efficient universality of quantum circuits
  3. Quantum circuit synthesis over Clifford+T

    II. Quantum algorithms for algebraic problems

  4. The abelian quantum Fourier transform and phase estimation
  5. Discrete log and the hidden subgroup problem
  6. The abelian HSP and decomposing abelian groups
  7. Quantum attacks on elliptic curve cryptography
  8. Quantum algorithms for number fields
  9. Period finding from ℤ to ℝ
  10. Quantum query complexity of the HSP
  11. Fourier analysis in nonabelian groups
  12. Fourier sampling
  13. Kuperberg’s algorithm for the dihedral HSP
  14. The HSP in the Heisenberg group
  15. Schur-Weyl duality
  16. Approximating the Jones polynomial

    III. Quantum walk

  17. Continuous-time quantum walk
  18. Discrete-time quantum walk
  19. Unstructured search
  20. Quantum walk search

    IV. Quantum query complexity

  21. Query complexity and the polynomial method
  22. The collision problem
  23. The quantum adversary method
  24. Span programs and formula evaluation
  25. Learning graphs

    V. Quantum simulation

  26. Simulating Hamiltonian dynamics
  27. Fast quantum simulation algorithms
  28. Quantum signal processing

    VI. Adiabatic quantum computing

  29. The quantum adiabatic theorem
  30. Adiabatic optimization
  31. An example of the success of adiabatic optimization
  32. Universality of adiabatic quantum computation