Quantum algorithms (CMSC 858Q, Spring 2017)

Announcements

Course topics

This is an advanced graduate course on quantum algorithms for students with prior experience in quantum information. The course will cover algorithms that allow quantum computers to solve problems faster than classical computers. Topics will include the quantum circuit model, quantum algorithms for algebraic problems (computing discrete logarithms, the hidden subgroup problem, quantum algorithms for number fields), quantum search, quantum walk algorithms, quantum algorithms for simulating quantum mechanics, limitations on the power of quantum computers, and selected recent developments in quantum algorithms.

Coordinates

Time: Tuesday/Thursday, 12:30–1:45 pm
Location: CSI 3118

Instructor

Andrew Childs
Email: amchilds@umd.edu
Office: CSS 3100F, AVW 3225
Office hours: Tuesdays, 2–3 pm, AVW 3225; Wednesdays, 3:30–4:30 pm, CSS 3100F; also available by appointment

Prerequisites

This course assumes a good working knowledge of linear and abstract algebra, as well as concepts in quantum information at the level of CMSC 858K: Introduction to Quantum Information Processing. In particular, you should already be familiar with the material reviewed in Chapter 1 of the lecture notes. 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 Lecture notes will be available for all topics covered in the class. The relevant chapters will be indicated on the schedule below. 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.

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). Grades will be recorded at grades.cs.umd.edu.

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 short 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 is available, 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@umd.edu by March 9.

You will have 20 minutes to give your presentation, with 5 minutes for questions. Presentations will be scheduled during the last several class meetings.

Your paper is due by May 11. 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.

Academic accommodations

Any student eligible for and requesting reasonable academic accommodations due to a disability is asked to provide, to the instructor during office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.

If you plan to observe any holidays during the semester that are not listed on the university calendar, please provide a list of these dates by the end of the first week of the semester.

In the event of a medical emergency that affects your ability to complete coursework, appropriate accommodations will be made. However, you must make a reasonable attempt to notify the instructor prior to the due date, and you must provide written documentation from the Health Center or an outside health care provider. This documentation must verify dates of treatment and indicate the timeframe that you were unable to meet academic responsibilities. It must also contain the name and phone number of the medical service provider in case verification is needed. No diagnostic information will ever be requested.

Course evaluations

Course evaluations are an important part of evaluating instruction. The Department of Computer Science and its faculty take student feedback seriously. Students can go to courseevalum.umd.edu to complete their evaluations.

Schedule

Note: The following schedule is tentative and subject to change.

DateTopicNotesReferencesDue
Jan 26 Preliminaries, quantum circuits, the Solovay-Kitaev theorem 2 [NC App. 3] [DN] [KSV Sec. 8]
Jan 31 Circuit synthesis over Clifford+T 3 [KMM] [GS]
Feb 2 Abelian QFT, phase estimation, computing discrete logarithms 4, 5 [CEMM] [Shor]
Feb 7 Hidden subgroup problem, abelian HSP 5, 6 [CD]
Feb 9 Factoring, Period finding from ℤ to ℝ, Pell’s equation 8, 9 [Shor] [Hal] [Joz]
Feb 14 The nonabelian HSP and its query complexity 10 [EHK]
Feb 16 Nonabelian Fourier analysis 11 [Serre]
Feb 21 Fourier sampling 12 [HRT] [GSVV] [MRS] [HMRRS] A1
Feb 23 Kuperberg’s algorithm for the dihedral HSP 13 [Kuperberg] [Regev]
Feb 28 Continuous-time quantum walk 1 16 [CCDFGS]
Mar 2 Continuous-time quantum walk 2
16
Mar 7 Discrete-time quantum walk 17 [Sze] [MNRS] [San]
Mar 9 Unstructured search, amplitude amplification, search on a graph 18 [Gro] [BHMT] [CG] [AKR] Topic
Mar 14 Element distinctness, quantum walk search 19 [Ambainis] [Santha]
Mar 16 Quantum query complexity, polynomial method 20 [BBCMW] [HS] A2
Mar 21 Class does not meet (spring break)
Mar 23 Class does not meet (spring break)
Mar 28 Polynomial method 2 21
Mar 30 Adversary lower bounds 22 [Amb] [HS] [SS] [HLS]
Apr 4 Span programs 1 23 [RS] [Rei]
Apr 6 Span programs 2 23
Apr 11 Learning graphs 24 [Bel] [BL]
Apr 13 Quantum simulation and product formulas 25 [Fey] [Lloyd] [BACS] A3
Apr 18 Fast quantum simulation algorithms 26 TBD
Apr 20 Quantum algorithm for linear systems 27 [HHL]
Apr 25 TBD
Apr 27 Final project presentations
May 2 Final project presentations
May 4 Final project presentations
May 9 Final project presentations
May 11 Final project presentations Paper