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