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.

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.

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.

- Lectures held Tuesday/Thursday, 11:00 am–12:15 pm on Zoom (meeting link on Canvas)
- Announcements/discussion on Piazza
- Assignment/exam problems on Canvas
- Assignment/exam submissions on Gradescope
- Office hours on Zoom (times listed below; meeting links on Canvas)

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

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.

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*

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

- Assignment 1:
*February 18* - Assignment 2:
*March 11* - Assignment 3:
*April 8*

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:

- a project proposal, due March 4 (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 paper (45%), due May 11.

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.

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.

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.

*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 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 | 23 | A3 | |

Apr 15 | Quantum simulation | 25 | [Fey] [Lloyd] [BACS] | |

Apr 20 | Post-Trotter simulation algorithms | 26 | [Chi] [BCCKS] | |

Apr 22 | Quantum signal processing | 27 | [LC] [GSLW] | |

Apr 27 | Quantum signal processing | 27 | ||

Apr 29 | Project presentations | |||

May 4 | Project presentations | |||

May 6 | Project presentations | |||

May 11 | Project presentations | Paper | ||

May 13 | Final exam | F |