- 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.

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

Location: MC 4064

Andrew Childs

Email: amchilds@uwaterloo.ca

Office: MC 4031

Office hours: Tuesday, 1–2:30 pm (or by appointment)

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
*Quantum algorithms for algebraic problems* (arXiv:0812.0380) by Childs and van Dam.

- Kaye, Laflamme, and Mosca,
*An Introduction to Quantum Computing*(errata) - Kitaev, Shen, and Vyalyi,
*Classical and Quantum Computation* - Nielsen and Chuang,
*Quantum Information and Quantum Computation*

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:

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

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.

Note: There is also an updated and expanded version of the lecture notes.