Format:

Each student will make one 70 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 15 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. Laptop projector, overhead transparencies and blackboard are all acceptable media and I harbor no preference among them. (Just beware the risks of each medium: blackboard lectures can degenerate into confusion if not carefully prepared and PowerPointers must act consciously to avoid powerpoints.) Be sure to leave a few minutes at the end to sum up and offer some perspective. There will be a ten 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 and Ambainis: Quantum search of spatial regions

4) Ambainis, Nayak, Ta-Shma and Vazirani: Dense quantum coding and a lower bound for 1-way quantum automata

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

6) Barnum, Saks and Szegedy: Quantum query complexity and semi-definite programming

7) Bar-Yossef, Jayram and Kerenidis: Exponential separation of quantum and classical one-way communication complexity

** **8) Childs and Eisenberg: Quantum algorithms for subset finding

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

10) Farhi, Goldstone, Gutman and Sipser: Invariant quantum algorithms for insertion into an ordered list

11) Fortnow and Rogers: Complexity limitations on quantum computation

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

13) Kuperberg: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem (see also these notes)

14) Watrous: Zero-knowledge against quantum attacks