Quantum algorithms (CO 781/CS 867/QIC 823, Winter 2011)


Course description

An investigation of algorithms that allow quantum computers to solve problems faster than classical computers. The quantum circuit model. Quantum Fourier transform, phase estimation, computing discrete logarithms, and quantum algorithms for number fields. The hidden subgroup framework and the nonabelian hidden subgroup problem. Quantum search, amplitude amplification, and quantum walk algorithms. Limitations on the power of quantum computers. Selected current topics in quantum algorithms.


Time: Tuesday/Thursday, 2:30–3:50 pm
Location: MC 4064


Andrew Childs
Email: amchilds@uwaterloo.ca
Office: MC 4031
Office hours: Tuesday, 1–2:30 pm (or by appointment)


This course assumes some knowledge of linear and abstract algebra, as well as basic concepts in quantum information at the level of AMATH 871/CO 681/CS 667/PHYS 767/QIC 710: Introduction to Quantum Information Processing. You are encouraged to consult with the instructor if you are unsure whether you are prepared to take the course.


There is no required textbook. Good sources of background material include Most of the material on the hidden subgroup problem and related concepts (roughly the first half of the course) is covered in the survey article Quantum algorithms for algebraic problems (arXiv:0812.0380) by Childs and van Dam.

Lecture notes will be posted on the course schedule below, along with links to relevant research papers and surveys.


Grades for the course will be based on three assignments (each worth 20% of the final grade) and a final project consisting of a term paper and short presentation (40% of the final grade).


Assignments will be made available here. You are encouraged to discuss the problems with your colleagues and the instructor and to consult the research literature. However, your solutions should be written independently, based on your own understanding, and you should acknowledge whatever resources you consulted. The assignments are due in class as follows:

Final project

The final project for the course will consist of an expository paper and a brief presentation to the class on a recent topic related to quantum algorithms. You may either select from a list of suggested topics or choose an alternative topic in consultation with the instructor. Each student should have a unique topic. Please send an email message specifying your desired topic to amchilds@uwaterloo.ca by Tuesday 8 March.

You will have 25 minutes to give your presentation, with 5 minutes for questions. Presentations will be scheduled during the last two class meetings (29 and 31 March), with additional times scheduled as necessary.

Your paper is due on Tuesday 12 April. It should be typeset in LaTeX and submitted by email as a PDF file. There are no length requirements, but as a rule of thumb, your paper should be around 10 pages.


4 Jan Preliminaries, quantum circuits, the Solovay-Kitaev theorem [NC App. 3] [DN] [KSV Sec. 8]
6 Jan Abelian QFT, phase estimation [CEMM]
11 Jan Class does not meet (QIP 2011)—to be rescheduled
13 Jan Class does not meet (QIP 2011)—to be rescheduled
18 Jan Hidden subgroup problem, computing discrete logarithms [Shor]
20 Jan Abelian HSP, decomposing abelian groups [CM]
24 Jan Pell's equation
(Makeup lecture, 2:30–4 pm, MC 5136)
[Hal] [Joz] [Amb (2-7 Mar)]
25 Jan Period finding from ℤ to ℝ
26 Jan The nonabelian HSP and its query complexity
(Makeup lecture, 2:30–4 pm, MC 5136)
27 Jan Nonabelian Fourier analysis [Serre]
1 Feb Fourier sampling [HRT] [GSVV] [MRS] [HMRRS]
3 Feb Kuperberg's algorithm for the dihedral HSP [Kuperberg] [Regev] [CJS]
8 Feb HSP in the Heisenberg group [BCD]
10 Feb Simulating Hamiltonian dynamics [Fey] [Lloyd] [BACS]
15 Feb Continuous-time quantum walk [CCDFGS]
17 Feb Discrete-time quantum walk [Sze] [Vaz] [MNRS] [San]
22 Feb Class does not meet (reading week)
24 Feb Class does not meet (reading week)
1 Mar Unstructured search [Gro] [BHMT] [CG] [AKR]
3 Mar Element distinctness [Ambainis]
8 Mar Formula evaluation 1 [FGG] [ACRSZ] [RS]
10 Mar Formula evaluation 2
15 Mar Adversary lower bounds [Amb] [SS] [HLS]
17 Mar Adversary lower bounds continued
22 Mar Polynomial method [BBCMW]
24 Mar Lower bound for the collision problem [Aar] [AS] [Kut]
29 Mar (2–4 pm, MC 5158) Final project presentations
31 Mar (2–4 pm, MC 4062) Final project presentations