Quantum Reading Seminar

Fall 2005:

Thursdays, 11:00-13:00, Ross (location will be announced later).

Organizer: Dorit Aharonov

In this seminar we will read and understand some of the recent papers in quantum computation. Attendants ( students and researchers and by-passers) will be assumed to have some (not too much, though) background in quantum computation, or quantum information (or be willing to learn the necessary material on their own). The seminar can be taken for credit of two points. The grade will be on the basis of pass\fail, and a pass grade will require understanding and presenting one paper, and attendance to some reasonable percentage of the talks. For a list of suggested papers, see below the table. Students - please have a look and let me know your preference.




Date	Paper	Speaker
3/11/05	A survey of quantum computation	Dorit Aharonov
10/11/05	The symmetric group and quantum computation See The hidden subgroup problem and permutation group theory Joint seminar with Algebra Seminar, Location Math 209!!!	Aner Shalev
17/11/05	A Polynomial Quantum Algorithm for Approximating the Jones Polynomial By Aharonov, Jones and Landau. Can be downloaded here.	Dorit Aharonov
24/11/05	Zero Knowledge against quantum attacks (2005) John Watrous	Michael Ben-Or
1/12/05	We will complete the previous paper, and: Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games (2002) Terhal & Divincenzo	Itai Arad
8/12/05	Canceled due to sickness of speaker... Instead there was a colloquium about the quantum algorithm of the Jones polynomial at 4:00.
15/12/05	A geometric approach to quantum circuit lower bounds (2005) Nielsen	Evgeny Begelfor
22/12/05	We all went to Avi Wigderson's talk.
29/12/05	The computational complexity of the Tutte and Jones polynomials Jaeger, Vertigan, Welsh	Elad Eban
5/1/05	Algebraic and information-theoretic conditions for operator quantum error-correction (2005) Nielsen and Poulin	Yonatan Most
12/1/06	Universal Quantum Computation with ideal Clifford gates and noisy ancillas (2004) Sergei Bravyi, Alexei Kitaev	Yossi Appelbaum
19/1/05	Canceled due to the annual conference on Quantum Information Processing.
26/1/06	Continued: Universal Quantum Computation with ideal Clifford gates and noisy ancillas (2004) Sergei Bravyi, Alexei Kitaev	Yossi Appelbaum
2/2/06	The Complexity of the Local Hamiltonian Problem (2004) Kempe, Kitaev and Regev	Or Sattath


Possible papers, sorted by topics. Any other interesting paper will be wellcome.

Topic	Paper	Authors
Foundations of the Model	Efficient classical simulation of slightly entangled quantum computations and Efficient simulation of one-dimensional quantum many-body systems (2003)	Vidal
	The Solovay-Kitaev algorithm (2005) Can be downloaded here.	Dawson, Nielsen
Algorithms	Quantum algorithm for a generalized hidden shift problem (2005)	Andrew M. Childs, Wim van Dam
	Quantum Algorithms for Matching and Network Flows (2005)	Andris Ambainis
Topological Quantum Computation	The Jones Polynomial and the Potts model
Error Correction & Fault Tolerance	Quantum Computing with Very Noisy Devices (2004)	Knill
	Improved ancilla preparation scheme increases fault-tolerant threshold (2004)	Reichardt
	Consequences and Limits of Nonlocal Strategies (2004)	Cleve, Hoyer, Toner, and Watrous
Quantum & Bad Guys	A large family of quantum weak coin-flipping protocols (2005) Quantum weak coin-flipping with bias of 0.192 (2004)	Mochon
	Fast quantum byzantine agreement (2005)	Ben-Or and Hassidim
	Superselection rules and quantum protocols (2005)	Alexei Kitaev, Dominic Mayers, John Preskill