Quantum algorithms (CO 781, Winter 2008): Final project
The final project for CO 781 will consist of an expository paper and a brief presentation to the class on a recent topic related to quantum algorithms. You may either select from the list of suggested topics below, or choose an alternative topic in consultation with the instructor. Please send an email message specifying your chosen topic to Prof. Childs by Tuesday 4 March.
You will have 25 minutes to give your presentation, with 5 minutes for questions. Presentations will be scheduled during the final week of class (1 and 3 April), with additional times scheduled as necessary.
Your paper is due on Monday 14 April. It should be typeset in LaTeX and submitted to Prof. Childs by email (as a PDF file). There are no length requirements, but as a rule of thumb, your paper should be around 10 pages.
The following is a list of potential topics, with one or two key references for each.
- Hidden subgroup problem
- The connection between the dihedral HSP and lattice problems [Reg]
- Quantum algorithms for hidden shift problems [DHI]
- Quantum reductions for the HSP: Hidden translation and orbit coset [FIMSS]
- Entangled measurements are required for the symmetric group [MRS] [HMRRS]
- Algorithms for the HSP in extraspecial and nil-2 groups [ISS1] [ISS2]
- Sieve algorithms beyond Kuperberg [AMR] [Bac]
- Quantum walk
- Verifying matrix products [BS]
- Testing group commutativity [MN]
- Generalized framework for quantum walk search algorithms [MNRS]
- Span program-based algorithm for formula evaluation [RS]
- Adiabatic quantum computation
- 3SAT formulas that are hard(?) for adiabatic optimization [DV] [FGG]
- Adiabatic state generation and SZK [AT]
- Universal adiabatic quantum computation with improved locality [KKR] [OT]
- Error-correcting codes for adiabatic quantum computation [JFS]
- Other topics
- Quantum algorithms for solvable groups [Wat]
- Searching an ordered list [FGGS] [HNS]
- Quantum query complexity and semidefinite programming [BSS]
- Quantum algorithms for approximating the Jones polynomial [AJL] [WY]