The final project for the course will consist of a paper and a brief 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. 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@uwaterloo.ca by *Tuesday 12 March*.

You will have 25 minutes to give your presentation, with 5 minutes for questions. You are encouraged to give a computer presentaton; a data projector will be available. Presentations will be during the last two class meetings (*2 and 4 April*), with an additional hour on Thursday. See below for a detailed schedule.

Your paper is due on *Tuesday 11 April*. 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.

- Hidden subgroup problem
- 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] [Rötteler]
- Quantum reductions for the HSP: Hidden translation and orbit coset [FIMSS]
- Entangled measurements are required for the symmetric group [MRS] [HMRRS]
- Sieve algorithms beyond Kuperberg [AMR] [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]

- Quantum query complexity
- Multiplicative adversary method [Spalek]
- Lower bounds for quantum state generation [AMRR]
- Time-space tradeoffs [KSW]
- Limitations on quantum algorithms for symmetric functions [AA]
- Learning graph algorithm for
*k*-distinctness [Belovs] - Learning graph algorithms for subgraph finding and associativity testing [LMS]

- Other topics

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

Tuesday 2 April | ||

2:30 | Vincent Russo | Quantum algorithms for linear equations |

3:00 | Young Han | Quantum query algorithms using nested quantum walks |

3:30 | Shitikanth Kashyap | Testing symmetric properties of distributions |

Thursday 4 April |
||

2:30 | Stacey Jeffery | Understanding the need for structure in quantum speedups using representations |

3:00 | Srinivasan Arunachalam | Quantum algorithms for solvable groups |

3:30 | Brandon Weir | The dihedral HSP and learning with errors |

4:00 | Alex Valtchev | Search on a grid and the quantum walk search framework |

4:30 | Zak Webb | Limitations on quantum algorithms for symmetric functions |