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

Announcements

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

Time: Tuesday/Thursday, 2:30–3:50 pm
Location: QNC 1201

Instructor

Andrew Childs
Email: amchilds@uwaterloo.ca
Office: QNC 3126
Office hours: Monday, noon–1:30 pm (also available by appointment)

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

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

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:

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.

Schedule

DateTopicReferences
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

Note: Some additional topics were covered in previous versions of the course in Winter 2008 and Winter 2011. There is also an updated and expanded version of the lecture notes.