CS 411 Directed Study in Computer Science
Readings in Quantum Computation
Course Syllabus -- Fall 1997

Instructor: C. Tamon
Office: SC369
Phone: x6521
email: tino@sun.mcs

Office Hours: M,W 2:00-4:00 p.m. and F 2:00-3:00 (tentative)

Syllabus: This course will discuss some recent works in quantum computation. Tentative topics include efficient quantum algorithms for promise problems (Simon's problem), factoring and discrete logarithms (Shor's algorithm), searching, and other database problems (Grover's algorithms).

Tentative topics and reading list:

  1. Basics
    • Berthiaume, Andre. Quantum Computation. Manuscript.
  2. Promise problems (period-finding problems)
    • Shor, Peter. Polynomial-time algorithms for factoring and discree logarithms on a quantum computer. To appear in SIAM Journal on Computing.
    • Simon, Daniel. On the Power of Quantum Computation. In Proceedings of the IEEE 35th Annual Symposium on Foundations of Computer Science, pages 116-123, 1994.
  3. Database problems
    • Grover, Lov. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pages 212-219, 1996.
    • Boyer, Michel, Brassard, Giles, Hoyer, Peter, and Tapp, Alain. Tight Bounds for Quantum Searching. Los Alamos preprint, 1996.
  4. Communication complexity
    • Buhrman, Harry, Cleve, Richard, and van Dam, Wim. Quantum Entanglement and Communication Complexity. Manuscript, 1997.

    Prerequisites: Abstract Linear Algebra and Probability Theory.

    Policies: Refer to Clarkson Regulations 1997 for policies on Academic Integrity, Code of Ethics, Sanctions and other matters related to plagiarism.