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

Announcements

15 Mar: A schedule for the final project presentations has been posted.

13 Mar: Part d of problem 5 on assignment 3 has been corrected.

11 Mar: Project presentations will be on 29 and 31 March, and will be from 2–4 pm (i.e., starting half an hour earlier than usual). We will meet in MC 5158 on 29 March and in MC 4062 on 31 March.

22 Feb: Suggested project topics have been posted.

17 Feb: Solution to problem 1(a)ii of assignment 1

30 Jan: For problem 5a on assignment 1, you may assume that the classical computer uses a deterministic algorithm (although a similar lower bound holds for randomized algorithms).

26 Jan: Office hours will be canceled on Tuesday, February 1. Instead there will be office hours from 2:30–4 pm on Monday, January 31.

26 Jan: Enrollment is now open for CS 867.

24 Jan: For problem 3 on assignment 1, you should assume that the elements of G have a unique representation and that you can efficiently compute products and inverses.

18 Jan: Office hours have been scheduled for Tuesdays from 1–2:30 pm in MC 4031. Makeup lectures have been scheduled for Monday, January 24, and Wednesday, January 26, from 2:30–4 pm in MC 5136.

6 Jan: Please remember that there will be no class on 11 or 13 January.

29 Dec: Enrollment for CS 867 is currently listed as closed on Quest even though there is still plenty of room in the class for additional students. The registrar's office has been notified, but due to the holidays the issue may not be resolved until the term begins. Note that you should still be able to register for CO 781 or QIC 823.

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.

Coordinates

Instructor

Prerequisites

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.

References

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.

Evaluation

Assignments

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:

Assignment 1: Tuesday 1 February
Assignment 2: Tuesday 1 March
Assignment 3: Tuesday 29 March

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.

Date	Topic	References
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)	[EHK]
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

Date

Topic

References

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