Assignments of papers to students in Tel Aviv and in Hebrew University

Instructions for the lectures.

Entanglement

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

(*) Conditions for a class of entanglement transformations M. A. Nielsen

(*) 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

Communication and Cryptography

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

(*) ($$) A new protocol and lower bounds for quantum coin flipping By Andris Ambainis

Interaction in Quantum Communication Complexity Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

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

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

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

Algorithms

($$) Normal subgroup reconstruction and quantum computation using group representations A. Russell, S. Hallgren and A. Ta-Shma (paper can be downloaded from Amnon's webpage

(*) Quantum Ordered Searching Peter Hoyer and Jan Neerbek.

(*) A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, Daniel Preda

(*) ($$) Quantum algorithms for Solvable groups by John Watrous.

Succinct quantum proofs for properties of finite groups by John Watrous.

(*) ($$) Quantum Walks On Graphs By Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani

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

(*) Mixed State Entanglement and Quantum Error Correction By Charles H. Bennett, David P. DiVincenzo, John A. Smolin, William K. Wootters

(*) 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)