Quantum algorithms (CMSC 858Q, Spring 2021)

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 quantum circuits, quantum algorithms for algebraic problems (computing discrete logarithms, the hidden subgroup problem, quantum algorithms for number fields), quantum walk algorithms, quantum algorithms for simulating quantum mechanics, limitations on the power of quantum computers, and selected recent developments in quantum algorithms.

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

Class format

This class will be held virtually, with no in-person meetings. We will have synchronous lectures on Zoom, which will be recorded and made available through Canvas (also referred to as ELMS). We will reevaluate this format as the semester progresses and may make adjustments.

Coordinates

Course staff

EmailOffice hours (meeting links on Canvas)
Andrew Childs (Instructor) amchilds@umd.edu Monday, 2:30–3:30 pm; Thursday, 12:15–1:15 pm
Daochen Wang (TA) daochen@umd.edu Friday, 3–4 pm

Piazza

We will use Piazza for class announcements and discussion. You should sign yourself up for the course Piazza page. Instead of emailing questions to the teaching staff, please post questions on Piazza. You are encouraged to post questions publicly when possible so the whole class can benefit from the discussion, though you can also post private questions for any personal issues.

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 lecture schedule below.

Evaluation

Grades for the course will be based on three assignments (each worth 13% of the course grade), a course project to be presented in the last few weeks of the semester (31% of the course grade), and a final exam (30% of the course grade).

Assignments

There will be three assignments, which will be made available on Canvas. 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 will be due on Gradescope as follows:

Project

For the course project, you will study 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 also include some original research contributions. A list of suggested topics is available, but you are free to choose a topic not on that list. You may choose to work alone or with a group of two or three students. Each group should have a unique topic.

Your project will include the following deliverables:

Further details will be provided in class and on Piazza as the course progresses.

Final exam

The course will include a comprehensive, take-home final exam. The exam will be made available on the morning of Thursday, May 13, and will be due by 11:59 pm the same day (via Gradescope). You may choose to take the exam during any three-hour period that day.

Course policies and academic accommodations

We will follow the standard University of Maryland graduate course policies. You should be familiar with them.

Any student eligible for and requesting reasonable academic accommodations due to a disability is asked to provide, to the instructor by email, a letter of accommodation from the Accessibility and Disability Service (ADS) office 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 two weeks of the semester.

Course evaluations

Student feedback is an important part of evaluating instruction. The Department of Computer Science takes this feedback seriously and appreciates your input. Toward the end of the semester, please go to www.courseevalum.umd.edu to complete your evaluation.

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 28 Solovay-Kitaev theorem 2
Feb 2 Clifford+T circuit synthesis 3 [KMM] [GS]
Feb 4 Abelian QFT, phase estimation, computing discrete logarithms 4, 5 [CEMM] [Shor]
Feb 9 Hidden subgroup problem, abelian HSP 5, 6 [CD]
Feb 11 Pell’s equation, Period finding from ℤ to ℝ 8, 9 [Hal] [Joz]
Feb 16 The nonabelian HSP and its query complexity 10 [EHK]
Feb 18 Nonabelian Fourier analysis 11 [Serre] A1
Feb 23 Fourier sampling 12 [HRT] [GSVV] [MRS] [HMRRS]
Feb 25 Kuperberg’s algorithm for the dihedral HSP 13 [Kuperberg] [Regev]
Mar 2 Kuperberg’s algorithm, Continuous-time quantum walk 13,16 [CCDFGS]
Mar 4 Continuous-time quantum walk 16 Proposal
Mar 9 Discrete-time quantum walk 17 [Sze] [MNRS] [San]
Mar 11 Unstructured search, amplitude amplification, search on a graph 18 [Gro] [BHMT] [CG] [AKR] A2
Mar 16 Class does not meet (spring break)
Mar 18 Class does not meet (spring break)
Mar 23 Element distinctness, quantum walk search 19 [Ambainis] [Santha]
Mar 25 Quantum query complexity, polynomial method 20 [BBCMW] [HS]
Mar 30 Polynomial method 21 [Kut]
Apr 1 Polynomial method, Adversary method 22
Apr 6 Adversary lower bounds 23 [Amb] [HS] [SS] [HLS]
Apr 8 Adversary dual 23 [RS] [Rei]
Apr 13 Adversary dual 25 A3
Apr 15 Quantum simulation 26 [Fey] [Lloyd] [BACS]
Apr 20 Post-Trotter simulation algorithms 27
Apr 22 Block encoding and quantum signal processing TBD TBD
Apr 27 Block encoding and quantum signal processing TBD TBD
Apr 29 Project presentations
May 4 Project presentations
May 6 Project presentations
May 11 Project presentations Paper
May 13 Final exam F

Web Accessibility