411 Directed Study in Computer Science
Readings in Quantum Computation
Course Syllabus -- Fall 1997
Instructor: C. Tamon
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:
- Berthiaume, Andre. Quantum Computation. Manuscript.
- 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.
- 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,
- Communication complexity
- Buhrman, Harry, Cleve, Richard, and van Dam, Wim. Quantum
Entanglement and Communication Complexity. Manuscript, 1997.
Prerequisites: Abstract Linear Algebra and Probability
Policies: Refer to Clarkson Regulations 1997 for
policies on Academic Integrity, Code of Ethics, Sanctions and other
matters related to plagiarism.