Course Announcement -- Quantum Computation
------------------------------------------

Teachers: Amnon Ta-Shma and Oded Regev
Semester: A+B (Spring 2005 + Fall 2006)
Time: Thursday 12:00-15:00
Web: http://www.cs.tau.ac.il/~odedr/teaching/quantum_fall_2005/index.html

This year-long course covers the recent progress on quantum computation,
starting from early algorithms, through Shor's groundbreaking factoring algorithm,
and ending in some very recent research topics.

The course material should be of interest to computer scientists, physicists, and mathematicians.
No familiarity with quantum mechanics is required. It would also be useful to know something about
classical complexity theory, and some basic linear algebra (but we will review this material when
we get to it).

Final grade is based on attendance and 4-5 problem sets.

Some of the topics planned for semester A:
* Brief introduction to the quantum computation model
* Bell inequalities and teleportation
* Quantum algorithms:
   - Deutsch-Jozsa, and Simon
   - The Hidden Subgroup Problem
   - Phase estimation
   - Shor's factoring algorithm and discrete log
* More on the quantum model:
   - Measurements, density matrices, POVMs
   - Trace norm
   - Fidelity
   - SVD
* On bit commitment and coin flipping
* Grover's search algorithm, and lower bounds on query algorithms
* Quantum key distribution


Semester B will include some very recent research topics, including:
* Random walk algorithms
* Ambainis's distinctness algorithm
* Raz's PCP-based quantum states
* The diamond norm and its applications
* Quantum interactive proofs (QIP)
* Quantum Communication Complexity

Some recommended books:
  * Quantum Computation and Quantum Information, by Michael Nielsen and Isaac Chuang
  * Classical and Quantum Computation, by A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi