Quantum algorithms (CMSC 858Q, Spring 2025)

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, quantum walk algorithms, quantum algorithms for simulating quantum mechanics, limitations on the power of quantum computers, and selected recent developments in quantum algorithms.

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.

	Email	Office hours
Andrew Childs (Instructor)	amchilds@umd.edu	Tuesday, 3–4 pm, ATL 3359; Wednesday, 10–11 am, Zoom (link on Canvas)
Joseph Carolan (TA)	jcarolan@umd.edu	Monday, noon–1 pm, location TBD

We will use Piazza for class announcements and discussion. You should sign yourself up for the course Piazza page. This is the best way to stay up to date on what is happening in the course and to quickly get help from classmates, TAs, and the instructor. Instead of emailing questions to the teaching staff, please post questions on Piazza. You can send private posts to the instructors to discuss personal issues or solution details for an open assignment, but you should make posts public whenever possible so that everyone in the class can benefit from the discussion. The course staff may change the visibility of posts when appropriate. Please do not send messages to the course staff using the Canvas messaging system.

There is no required textbook. Good sources of background material include

• 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 available for all topics covered in the class. The relevant chapters will be indicated on the lecture schedule.

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

There will be three assignments, which will be made available on Canvas and should be submitted using Gradescope. 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 any resources you consulted. The assignments will be due as follows:

• Assignment 1: February 19
• Assignment 2: March 12
• Assignment 3: April 16

For the course project, you will study a topic related to quantum algorithms that goes beyond the material covered in the lectures. In addition to reviewing previous work on your topic, you should identify new research directions, and outstanding projects will include some original research contributions. A list of suggested topics will be provided, 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:

• a project proposal, due March 5 (10% of your project grade);
• a presentation to the class, to be scheduled during lecture times in the last few weeks of the semester (45%); and
• a written report (45%), due May 9.

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

The course will include a comprehensive, take-home final exam. The exam will be made available on the morning of Thursday, May 15 (the day of the registrar-assigned final exam slot), 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.

The following schedule is tentative and will be adjusted as the semester progresses. The classes on February 25 and 27 will either be rescheduled or held asynchronously due to the QIP 2025 Conference.

Date	Topic	Notes	References	Due
Jan 28	Preliminaries, quantum circuits, the Solovay-Kitaev theorem	2	[NC App. 3] [DN] [KSV Sec. 8]
Jan 30	Solovay-Kitaev theorem	2
Feb 4	Clifford+T circuit synthesis	3	[KMM] [GS]
Feb 6	Abelian QFT, phase estimation, computing discrete logarithms	4, 5	[CEMM] [Shor]
Feb 11	Hidden subgroup problem, abelian HSP	5, 6	[CD]
Feb 13	Nonabelian HSP and its query complexity	10	[EHK]
Feb 18	Nonabelian Fourier analysis	11	[Serre]	A1 (Feb 19)
Feb 20	Fourier sampling	12	[HRT] [GSVV] [CD]
Feb 25	(To be rescheduled) Kuperberg’s algorithm for the dihedral HSP	13	[Kuperberg] [Regev]
Feb 27	(To be rescheduled) Schur-Weyl duality	TBD	TBD
Mar 4	Continuous-time quantum walk	16	[CCDFGS]	Proposal (Mar 5)
Mar 6	Discrete-time quantum walk	17	[Szegedy]
Mar 11	Unstructured search, amplitude amplification, search on a graph	18	[Grover] [BHMT] [AKR]
Mar 13	Element distinctness, quantum walk search	19	[Ambainis] [MNRS] [Santha]	A2 (Mar 12)
Mar 18	Class does not meet (spring break)
Mar 20	Class does not meet (spring break)
Mar 25	Quantum query complexity, polynomial method	20	[BBCMW] [HS]
Mar 27	Polynomial method	21	[Kutin]
Apr 1	TBD	TBD	TBD
Apr 3	Adversary method	22	[Ambainis] [HS] [SS] [HLS]
Apr 8	Adversary lower bounds	22
Apr 10	Dual of the adversary method	23	[RS] [Reichardt]
Apr 15	Quantum simulation, product formulas	25	[Feynman] [Lloyd] [BACS] [CSTWZ]	A3 (Apr 16)
Apr 17	Post-Trotter simulation algorithms	26	[Childs] [BCCKS]
Apr 22	Quantum signal processing	27	[LC] [GSLW] [Lin]
Apr 24	Ground state preparation	TBD	TBD
Apr 29	Simulating fermions	TBD	TBD
May 1	Project presentations
May 6	Project presentations
May 8	Project presentations			Paper (May 9)
May 13	Project presentations
May 15	(Take home) Final exam			F

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

If you use an AI tool to assist in any course work (including assignments and the course project), you must disclose this in your submission, including the name of the tool and how it was used. Any use of AI tools on assignments must be consistent with the policy that the submitted work should be based on your own understanding. Your project paper should not contain any text produced by an AI tool.

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

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.