Quantum algorithms (CMSC 858Q, Spring 2017)

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

Instructor

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.

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

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: February 21
Assignment 2: March 16
Assignment 3: April 20

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

Schedule

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

Date	Topic	Notes	References	Due
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	Pell’s equation	8	[Hal] [Joz]
Feb 14	Period finding from ℤ to ℝ	9	[Hal] [Joz]
Feb 16	The nonabelian HSP and its query complexity	10	[EHK]
Feb 21	Nonabelian Fourier analysis	11	[Serre]	A1
Feb 23	Nonabelian Fourier analysis, Fourier sampling	11, 12
Feb 28	Fourier sampling	12	[HRT] [GSVV] [MRS] [HMRRS]
Mar 2	Kuperberg’s algorithm for the dihedral HSP	13	[Kuperberg] [Regev]
Mar 7	Continuous-time quantum walk	16	[CCDFGS]
Mar 9	Continuous-time quantum walk	16		Topic
Mar 14	Discrete-time quantum walk	17	[Sze] [MNRS] [San]
Mar 16	Discrete-time quantum walk	17		A2
Mar 21	Class does not meet (spring break)
Mar 23	Class does not meet (spring break)
Mar 28	Unstructured search, amplitude amplification, search on a graph	18	[Gro] [BHMT] [CG] [AKR]
Mar 30	Element distinctness, quantum walk search	19	[Ambainis] [Santha]
Apr 4	Quantum query complexity, polynomial method	20	[BBCMW] [HS]
Apr 6	Polynomial method	20
Apr 11	Adversary lower bounds	22	[Amb] [HS] [SS] [HLS]
Apr 13	Span programs	23	[RS] [Rei]
Apr 18	Span programs	23
Apr 20	Quantum simulation and product formulas	25	[Fey] [Lloyd] [BACS]	A3
Apr 25	Fast quantum simulation algorithms	26	[Chi]
Apr 27	Final project presentations
May 2	Final project presentations
May 4	Final project presentations
May 9	Final project presentations
May 11	Final project presentation; fast quantum simulation	26	[BCCKS]	Paper

Date

Topic

Notes

References

Due

Jan 26

Preliminaries, quantum circuits, the Solovay-Kitaev theorem

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

Jan 31

Circuit synthesis over Clifford+T

[KMM] [GS]

Feb 2