Format:
Each student will make one 25 minute presentation on a topic from the recent quantum computation literature. Most presentations will focus on a single research paper, but I am open to presentations that synthesize results from several papers. Presentations should be targeted to the other students in the class, who will likely not be familiar with the objectives, definitions and techniques used in the paper under consideration. Therefore, a significant amount of time should be devoted to motivating and introducing the problem, say roughly 12 minutes. Some effort should be made to explain the methods used in the paper even when a full description will be impossible due to the time constraint. Since the presentations will be short, you should prepare slides using LaTeX, PowerPoint or similar software. Be sure to leave a few minutes at the end to sum up and offer some perspective. There will be a five minute question period after each presentation.

Some tips:
Practice to make sure your presentation isn’t too long or too short.
Find a partner and practice again. Ask for constructive criticism.
Try to anticipate questions.
Be sure to explain all symbols on your slides.
(Don’t assume the audience has time to read them.)

Possible topics
(By no means exhaustive - feel free to suggest others):
1) Aaronson: Quantum computing, postselection, and probabilistic polynomial-time

2) Aaronson: The learnability of quantum states

3) Aaronson: BQP and the polynomial hierarchy

4) Aaronson and Ambainis: Quantum search of spatial regions

5) Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function

6) Bennett, Bernstein, Brassard and Vazirani: Strengths and weaknesses of quantum computing

7) Bacon, Childs and van Dam: From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups

8) Barnum, Saks and Szegedy: Quantum query complexity and semidefinite programming

9) Childs, Cleve, Deotto, Farhi, Gutmann and Spielman: Exponential algorithmic speedup by quantum walk

10) [Claimed by Artem Kaznatcheev] Childs, Reichardt, Spalek, Zhang: Every NAND formula can be evaluated in time N^{1/2+o(1)} on a quantum computer

11) Childs and Eisenberg: Quantum algorithms for subset finding

12) [Claimed by Constance Caramanolis] van Dam, Hallgren and Ip: Quantum algorithms for some hidden shift problems

13) van Dam, Mosca and Vazirani: How powerful is adiabatic quantum computation?

14) Durr, Heiligman, Hoyer and Mhalla: Quantum query complexity of some graph problems

15) [Claimed by Jeffrey Payette] Farhi, Goldstone, Gutmann and Sipser: Invariant quantum algorithms for insertion into an ordered list

16) Farhi and Gutmann: An analog analogue of digital quantum computation

17) Gottesman: An introduction to quantum error correction and fault-tolerant quantum computation

18) Ivanyos, Sanselme, Santha: An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups

19) Jain, Ji, Upadhyay and Watrous: QIP = PSPACE

20) [Claimed by Jonathan Cottrell] Kemme, Osborne, Vollbrecht, Poulin and Verstraete: Quantum Metropolis sampling

21) Kempe, Kitaev and Regev: The complexity of the local Hamiltonian problem

22) [Claimed by Julia Evans] Kuperberg: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem (see also these notes)

23) Magniez, Mayers, Mosca and Ollivier: Self-testing of quantum circuits

24) Watrous: Zero-knowledge against quantum attacks

Presentation possibilities (more options):

25) Buhrman, Cleve, Wigderson: Quantum vs. classical communication and computation

26) [Claimed by Anqi Xu] Gottesman: The Heisenberg representation of quantum computers

27) Hallgren's quantum algorithm for solving Pell's equation
Hallgren: Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
Jozsa: Notes on Hallgren's efficient quantum algorithm for solving Pell's equation

28) [Claimed by Alex Frechette] Harrow, Hassidim, Lloyd: Quantum algorithm for solving linear systems of equations

29) Kitaev's method for implementing the Fourier transform mod m for any m
Kitaev: Quantum measurements and the abelian stabilizer problem
Kitaev, Shen, Vyalyi: Classical and Quantum Computation (book)
Notes for Umesh Vazirani's quantum computation course

30) [Claimed by Andie Sigler] Markov, Shi: Simulating quantum computation by contracting tensor networks

31) [Claimed by Ali Assaf] Mitchison, Jozsa: Counterfactual computation

32) [Claimed by Hao Peng] Shi: Both Toffoli and controlled-NOT need little help to do universal quantum computation

33) [Claimed by Neil Edelman]: Laflamme et al.: Introduction to NMR Quantum Information Processing
Baugh et al.: Quantum information processing using nuclear and electron magnetic resonance: review and prospects

34) [Claimed by Jan Florjanczyk] Cubitt: Deciding whether a quantum channel is Markovian is NP-hard

35) Magniez, Nayak, Roland, Santha: Search via Quantum Walk

36) [Claimed by Dave Touchette] Arshed, Toor and Lidar: Channel Capacities of an Exactly Solvable Spin-Star System

37) [Claimed by Mahdi Milani Fard] Somma, Boixo and Barnum: Quantum Simulated Annealing

38) [Tomas Jochym-O'Connor] Mochon: Quantum Weak Coin-Flipping with Bias 0.192