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

Announcements

18 Apr: Project papers have been returned to your mailboxes.

16 Apr: Assignments 2 and 3 have both been graded and returned to your mailboxes (in QNC or MC as applicable).

26 Mar: The deadlines for assignment 3 and the course project have been extended. Assignment 3 will be due on April 9, and you are only asked to solve four out of the five problems. The paper for your course project will be due on April 16. These deadlines are firm.

22 Mar: Project presentations have been scheduled during the last week of lectures, on 2 and 4 April. To have enough time for all presentations, we will meet for an extra hour (until 5 pm) on Thursday 4 April. (Unfortunately QNC 1201 is not available for extra time on 2 April.) Time slots have been assigned at random; I am happy to make any change that everyone involved agrees to.

18 Mar: The due date for Assignment 3 has been extended until Tuesday 2 April.

28 Feb: Since the quantum walk search framework has not yet been covered in lecture, there will be an extension for the due date of Assignment 2 until Tuesday 12 March.

30 Jan: Makeup lectures will be held on Tuesday 5 February and Tuesday 12 February from 10–11:30 am in QNC 1102/1103.

17 Jan: A list of possible project topics has been added.

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 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, along with links to related research papers and surveys.

Evaluation

Assignments

There will be three assignments, which 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 5 February
Assignment 2: Tuesday 5 March
Assignment 3: Tuesday 2 April

Final project

The final project for the course will consist of a paper and a brief presentation to the class on a topic related to quantum algorithms. In addition to reviewing previous work on your topic, you should aim to identify new research directions; outstanding projects will include some original research contributions. A list of suggested topics will be provided, but you are free to choose a topic not on that list. Each student should have a unique topic. Please discuss your project with me and send an email message confirming your choice of topic to amchilds@uwaterloo.ca by Tuesday 12 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 (2 and 4 April), with additional times scheduled as necessary.

Your paper is due on Tuesday 11 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 probably be around 10 pages.

Date	Topic	References
8 Jan	Preliminaries, quantum circuits, the Solovay-Kitaev theorem	[NC App. 3] [DN] [KSV Sec. 8]
10 Jan	Abelian QFT, phase estimation, computing discrete logarithms	[CEMM] [Shor]
15 Jan	Hidden subgroup problem, abelian HSP	[CD]
17 Jan	Factoring, Pell’s equation, Period finding from ℤ to ℝ (part 1)	[Shor] [Hal] [Joz]
22 Jan	Class does not meet (QIP 2013)—to be rescheduled
24 Jan	Class does not meet (QIP 2013)—to be rescheduled
29 Jan	Factoring, Pell’s equation, Period finding from ℤ to ℝ (part 2)
31 Jan	The nonabelian HSP and its query complexity	[EHK]
5 Feb	Nonabelian Fourier analysis (Makeup lecture, 10–11:20 am, QNC 1102/1103)	[Serre]
5 Feb	Fourier sampling	[HRT] [GSVV] [MRS] [HMRRS]
7 Feb	Kuperberg’s algorithm for the dihedral HSP	[Kuperberg] [Regev]
12 Feb	Simulating Hamiltonian dynamics (Makeup lecture, 10–11:20 am, QNC 1102/1103)	[Fey] [Lloyd] [BACS]
12 Feb	Continuous-time quantum walk 1	[CCDFGS]
14 Feb	Continuous-time quantum walk 2
19 Feb	Class does not meet (reading week)
21 Feb	Class does not meet (reading week)
26 Feb	Discrete-time quantum walk 1	[Sze] [MNRS] [San]
28 Feb	Discrete-time quantum walk 2
5 Mar	Unstructured search, amplitude amplification, search on a graph	[Gro] [BHMT] [CG] [AKR]
7 Mar	Element distinctness, quantum walk search	[Ambainis] [Santha]
12 Mar	Quantum query complexity, polynomial method	[BBCMW] [HS]
14 Mar	Adversary lower bounds	[Amb] [HS] [SS] [HLS]
19 Mar	Span programs 1	[RS] [Rei]
21 Mar	Span programs 2
26 Mar	Learning graphs	[Bel] [BL]
28 Mar	Approximating the Jones polynomial	[AJL] [JS]
2 Apr	(2:30–4 pm) Final project presentations
4 Apr	(2:30–5 pm) Final project presentations

Date

Topic

References

8 Jan

Preliminaries, quantum circuits, the Solovay-Kitaev theorem

[NC App. 3] [DN] [KSV Sec. 8]

10 Jan

Abelian QFT, phase estimation, computing discrete logarithms

[CEMM] [Shor]

15 Jan

Hidden subgroup problem, abelian HSP

[CD]