0368.4467
Seminar on Quantum Computing

Announcements

• [Feb 28] The seminar will take place on Sundays, 15:00-17:00, in Physics 114.

Lecture notes

• Ofer Shayevitz on quantum compression

Possible Topics

• R. Cleve, P. Hoyer, B. Toner, J. Watrous, Consequences and Limits of Nonlocal Strategies. See also this paper.
• Z. Bar-Yossef, T. S. Jayram, I. Kerenidis, Exponential separation of quantum and classical one-way communication complexity, 2004.
• G. Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, 2003. And a related paper.
• B. M. Terhal, D. P. DiVincenzo, Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games, 2002.
• W. van Dam, G. Seroussi, Efficient Quantum Algorithms for Estimating Gauss Sums
• The local-Hamiltonian problem is QMA-complete. Included in the book by Kitaev et al., but also look here and here.
• A. Ambainis, L. Schulman, U. Vazirani, Computing with highly mixed states, 2000. And a related paper.
• A. Ambainis and A. Smith, Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption, 2004.
• D. Aharonov, V. Jones, and Z. Landau, A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
• S. Aaronson, Limitations of Quantum Advice and One-Way Communication, 2004.
• S. Bravyi, Efficient algorithm for a quantum analogue of 2-SAT, 2006.
• A. Razborov, An Upper Bound on the Threshold Quantum Decoherence Rate, 2003.
• A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, D. Spielman, Exponential algorithmic speedup by quantum walk. See also a survey.
• Search algorithms. Many recent papers, see this survey.
• The Solovay-Kitaev theorem. Included as an appendix to the book by Nielsen and Chuang. Also look here and here.
• S. Hallgren, Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem. Look also here and here.

Schedule