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. Approximating the Jones polynomial

    III. Quantum walk

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

    IV. Quantum query complexity

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

    V. Quantum simulation

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

    VI. Adiabatic quantum computing

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