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 will be provided, 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 amchilds@umd.edu 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.

The following is a list of some potential topics, with one or two key references for each. Of course, this list is necessarily incomplete. New topics may be added as the term progresses, and you are also welcome to choose a topic not on this list.

- Quantum algorithms for algebraic problems
- Quantum algorithm for counting points on algebraic curves [Kedlaya]
- Connection between the dihedral HSP and lattice problems [Regev]
- Quantum algorithms for hidden shift problems [DHI] [Roetteler]
- Quantum reductions for the HSP: Hidden translation and orbit coset [FIMSS]
- Entangled measurements are required for the symmetric group [MRS] [HMRRS]
- Quantum algorithms for arbitrary-degree number fields [EHKS]
- Unique sink orientation problem [Bacon]

- Quantum walk
- General framework for quantum walk search algorithms [MNRS]
- Verifying matrix products [BS]
- Testing group commutativity [MN]
- Minor-closed graph properties [CK]
- Quantum walks inspired by learning graphs [JKM] [BCJKM]
- Quantum walk speedup of backtracking algorithms [Montanaro]

- Quantum query complexity
- Learning graph algorithm for
*st*-connectivity [BR] - Learning graph algorithm for
*k*-distinctness [Belovs] - Lower bounds for quantum state generation [AMRR]
- Limitations on quantum algorithms for symmetric functions [AA]
- Adversary lower bounds for element distinctness, collision, and
*k*-sum [Belovs] [BS] [BR] - Time-space tradeoffs [KSW]
- Parallel quantum query complexity [JMW]
- Superquadratic separations for total functions [ABBLSS] [ABK]
- Sculpting quantum speedups [AB]

- Learning graph algorithm for
- Quantum simulation
- Quantum algorithms for quantum chemistry [BBKWLA] [RWSWT]
- Simulation by qubitization [LC]
- Laplacian linear systems and effective resistance [Wang]
- Quantum machine learning [Aaronson]

- Other topics

Time | Speaker | Topic |
---|---|---|

Thursday, April 27 | ||

12:30–12:55 | Yuan Su | Entanglement in measurement-based quantum computing |

12:55–1:20 | Troy Sewell | Tensor networks for approximating manifold invariants |

1:20–1:45 | Eddie Schoute | Query and time complexity of the triangle problem |

Tuesday, May 2 | ||

12:30–12:55 | Shih-Han Hung | Synthesis of multiqubit Clifford+T circuits |

12:55–1:20 | Aniruddha Bapat | Quantum property testing of groups |

1:20–1:45 | Aaron Ostrander | Span programs and ST connectivity |

Thursday, May 4 | ||

12:30–12:55 | Abhinav Deshpande | Quantum algorithms for finding thermal states |

12:55–1:20 | Sunandita Patra | Quantum walk speedup of backtracking algorithms |

1:20–1:45 | Alireza Seif | Universal quantum emulator |

Tuesday, May 9 | ||

12:30–12:55 | Tongyang Li | Quantum machine learning |

12:55–1:20 | Andrew Guo | Modern Hamiltonian simulation methods applied to quantum chemistry |

Thursday, May 11 | ||

12:30–12:55 | Keyi Liu | Generalized state preparation in simulation of field theories |