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.
|Office hours (meeting links on Canvas)|
|Andrew Childs (Instructor)||firstname.lastname@example.org||Monday, 2:30–3:30 pm; Thursday, 12:15–1:15 pm|
|Daochen Wang (TA)||email@example.com||Friday, 3–4 pm|
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:
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.
Note: The following schedule is tentative and subject to change.
|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|