Instructions for the lectures: The lectures should take 30 minutes, and can be given in any mode you prefer: Powerpoint presentation, transparancies, or a white board talk. After the lecture, there will be five minutes for questions. Please reherse the lecture at least once to make sure it fits 30 minutes! The main thing while preparing the talk is to UNDERSTAND the paper. This means much more than understanding every step in each proof (which is less important). You need to understand 1) the motivation for the questions asked in the paper. 2) The main results of the paper, and why it is interesting in the context of other things, 3) the intuition behind the proofs, what are the difficult points, where is the essential IDEA, not the technical points. Think about explaining the paper to your little nephew, rather than to the class... It will be best if you manage to email/talk to me before your lecture, to get some feedback.

The talks will take place starting 10:00, Tuesday, in 201 Ross building.

Entanglement

Classical simulation of quantum entanglement without local hidden variables By Serge Massar, Dave Bacon, Nicolas Cerf, Richard Cleve

Concentrating Partial Entanglement by Local Operations By Charles H. Bennett, Herbert J. Bernstein, Sandu Popescu, Benjamin Schumacher

Separability of Mixed States: Necessary and Sufficient Conditions Michal Horodecki, Pawel Horodecki, Ryszard Horodecki

Algorithms

Quantum Walk algorithm for element distinctness A. Ambainis

Quantum algorithms for some hidden shift problems W. van Dam, S. Hallgren, L. Ip

Quantum Ordered Searching Peter Hoyer and Jan Neerbek.

Notes on Hallgren's efficient quantum algorithm for solving Pell's equation Richard Josza

A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space Oded Regev

Quantum Walks On Graphs By Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani

Exponential algorithmic speedup by quantum walk Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman

Communication, Lower bounds, Cryptography

Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata A. Ambainis, A. Nayak, A. Ta-Shma, U. Vazirani

A new protocol and lower bounds for quantum coin flipping By Andris Ambainis

Quantum weak coin-flipping with bias of 0.192 Carlos Mochon

Quantum fingerprinting By Harry Buhrman (CWI), Richard Cleve (U Calgary), John Watrous (U Calgary), Ronald de Wolf (CWI)

Exact Quantum Algorithms for the Leader Election Problem S. tani, K. Matsumoto, ?

Exponential Separation of Quantum and Classical One-Way communication complexity Z. Bar-Yossef, T.S. Jayram and I. Kerenidis

Quantum Entanglement and the Communication Complexity of the Inner Product Function Richard Cleve, Wim van Dam, Michael Nielsen, Alain Tapp

The Quantum Communication Complexity of Sampling A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani and A. Wigderson

Exponential Separation of Quantum and Classical Communication Complexity Ran Raz (paper 29 on the list)

Effects of Noise, Physical realizations

Polynomial Simulations of Decohered Quantum Computers By Dorit Aharonov and Michael Ben-Or.

Bulk NMR Quantum Computation (I think this is the name of the paper) Gershenfeld Chuang, Science 275, 5298, 350-356, 1997

Scalable NMR Quantum Computation By Leonard J. Schulman, Umesh Vazirani

Separability of very noisy mixed states and implications for NMR quantum computing By S.L. Braunstein, C.M. Caves, R. Jozsa, N. Linden, S. Popescu, R. Schack

Computing with highly mixed states by Andris Ambainis, Leonard J. Schulman, Umesh Vazirani

Quantum to Classical Phase Transition in Noisy Quantum Computers By Dorit Aharonov

Quantum Complexity

Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. By Kitaev and Watrous (paper 8 on the list)

PSPACE has constant-round quantum interactive proof systems By Watrous (paper 10 on the list)