Quantum algorithms (CMSC 858Q, Spring 2017): Final project

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.

Suggested topics

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]
  
  
• 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
  • Searching an ordered list [FGGS] [HNS]
  • Quantum algorithms for solvable groups [Watrous]
  • Generic quantum speedups [HH] [BH]
  • Evaluating tensor networks [AL]

Web Accessibility