Quantum algorithms (CO 781, Winter 2008)

This course will cover recent developments in quantum algorithms. The objectives of the course are to bring graduate students up to speed with the state of the art in quantum algorithms, and to prepare them to work on research problems in quantum computing. The course will be roughly divided into three parts, on the hidden subgroup problem, quantum walk, and adiabatic quantum computation.

Coordinates

Time: 9:30–10:50 am, Tuesday/Thursday
Location: MC 5045

Instructor

Andrew Childs
Email: amchilds@uwaterloo.ca
Office: MC 4031
Office hours: Wednesday, 10:30 am–12 noon, or 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 CO 681/CS 667/PHYS 767: 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.

Textbook

There is no required textbook. Good sources of background material include Links to relevant research papers are provided below.

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

The course assignments are available below. You are encouraged to discuss the problems with your classmates and with the instructor, and to consult the research literature; but solutions to the problems should be written independently. 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. Please send an email message specifying your chosen topic to Prof. Childs by Tuesday 4 March.

You will have 25 minutes to give your presentation, with 5 minutes for questions. Presentations will be scheduled during the final week of class (1 and 3 April), with additional times scheduled as necessary.

Your paper is due on Monday 14 April. It should be typeset in LaTeX and submitted to Prof. Childs by email (as a PDF file). There are no length requirements, but as a rule of thumb, your paper should be around 10 pages.

Schedule

Note: Most of the material from lectures 1–10 has been incorporated into the review article Quantum algorithms for algebraic problems (arXiv:0812.0380), written with Wim van Dam.

8 Jan      Review of quantum computing; the abelian QFT
10 Jan The hidden subgroup problem; Shor's algorithm for discrete log [Sho]
15 Jan Quantum attacks on elliptic curve cryptography [PZ]
17 Jan Hallgren's algorithm for solving Pell's equation [Hal] [Joz] [Amb (2-7 Mar)]
22 Jan Period finding from ℤ to ℝ
24 Jan Query complexity of the general HSP [EHK]
29 Jan Class does not meet
31 Jan Class does not meet
4 Feb (RCH 208, 2:30–3:50 pm) Nonabelian Fourier analysis [Ser]
5 Feb Fourier sampling [HRT] [GSVV]
7 Feb Kuperberg's subexponential time algorithm for the dihedral group [Kup] [Reg]
11 Feb (RCH 208, 2:30–3:20 pm) Algorithm for the HSP in the Heisenberg group    [BCD]
12 Feb From random walk to quantum walk
14 Feb Simulating Hamiltonian dynamics
19 Feb Reading week—class does not meet
21 Feb Reading week—class does not meet
26 Feb Example of exponential speedup by quantum walk [CCDFGS]
28 Feb Szegedy's formulation of discrete-time quantum walk [Sze] [Vaz (13&14)]
4 Mar Unstructured search and spatial search [Gro] [CG1] [AKR] [CG2]
6 Mar Ambainis's algorithm for element distinctness [Amb]
11 Mar Quantum walk algorithm for formula evaluation [FGG] [ACRSZ]
13 Mar Formula evaluation continued
18 Mar The quantum adiabatic theorem [Teu (Ch. 2)] [JRS]
20 Mar Adiabatic optimization; adiabatic algorithm for unstructured search [FGGS] [RC] [DMV]
25 Mar Examples of success and failure of adiabatic optimization [LSM] [FGGS] [Rei]
27 Mar Universality of adiabatic quantum computation [ADKLLR]
1 Apr (MC 5158, 9:30 am–12 noon) Final project presentations
3 Apr (MC 5136B, 9:30 am–12 noon) Final project presentations