Instructions for the lectures: The lectures should take 25 minutes, and can be given in Powerpoint presentation, or transparencies. After the lecture, there will be five minutes for questions. At this point, you are supposed to answer questions asked also by the teacher... Please reherse the lecture at least once to make sure it fits 25 minutes - no extensions will be given. 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 quantum computation in general 3) the intuition behind the proofs, what are the difficult points, where is the essential IDEA, not (just) the technical points. Think about explaining the paper to your little nephew, rather than to the class. Please arrange a meeting with me at least a week before your lecture, to get some feedback and improvements. It may be that you will only need to present half of the paper, so the sooner you come to discuss this with me, the better. (we might actually have two meetings: one to agree on which parts to concentrate on, and the other a few days before the talk to discuss the plan for the talk.)

A list of papers will be put next to the door of my office, together with a paper with time slots. You should mark the paper you want with your name - first comes first take basis. You should also put your name in your preferred time slot.

On Monday the 8th of January I will survey the papers in class, so that you can make a wiser choice. Please try to have a look at those papers that might interest you before that. You can choose your paper even before Monday though.

Entanglement, foundations

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

Efficient simulation of one-dimensional quantum many-body systems By Guifre Vidal

Algorithms

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

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

Bounds on 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

Quantum search with variable times By Andris Ambainis

Quantum Algorithms for Matching and Network Flows By Ambainis and Spalek

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial By Dorit Aharonov, Vaughan Jones, Zeph Landau

Communication & 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)

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)

Quantum Complexity

Exponential Separation of Quantum and Classical Online Space Complexity By Francois Le Gall

Quantum Information and the PCP Theorem (paper 5 in that link), by R. Raz,

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)

On the Physics side: Noise and Physical realizations

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 (Only if you are familiar with representation theory of the symmetric group)

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

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