Introduction to Quantum Information Processing
CS 667, C&O 681, PHYS 767, AM 871
Fall 2009 (
http://www.cs.uwaterloo.ca/~cleve/courses/F09CS667/index.html)

Instructor
Richard Cleve (cleve@cs.uwaterloo.ca)

Office hours: after class or by appointment

Objectives
Quantum Information Processing (also known as "quantum computing") seeks to harness the strange power of quantum mechanics to provide a qualitatively different and more powerful way of processing information than "classical" physics seems to allow. The objective of this course is to introduce this multidisciplinary subject at the graduate level.

Topics to be covered
Detailed syllabus: [PDF]
Overview
(timing information is approximate):
   
Introduction to the quantum information framework (3 lectures).
    Quantum algorithms and complexity theory (8 lectures).
    Density matrices and quantum operations on them (3 lectures).
    Distance measures between quantum states (1 lecture).
    Entropy and noiseless coding (1 lecture).
    Error-correcting codes and fault-tolerance (3 lectures).
    Nonlocality (2 lectures).
    ○ Cryptography (3 lectures).

Intended audience
This course is mainly intended for graduate students in CS, C&O or Physics. Other students may take this course with the permission of the instructor.
Prerequisites are MATH 235 or equivalent (e.g. PHYS 364 & 365); STAT 230 or equivalent. Note: this course cannot be taken for credit by students who have taken CO 481 / CS 467 / PHYS 467.

Evaluation
5 assignments 12% each
1 project 40%

Assignments (worth 60% of the final grade)
Assignment 1 (due September 29)

Assignment 2 (due October 13)
Assignment 3 (due October 27)
Assignment 4
(due November 12)
Assignment 5 (due December 3)

Lecture notes from Fall 2008
Lectures 1-3        [PPT, PDF]

Lectures 4-6        [PPT, PDF]
Lectures 7-9        [PPT, PDF]
Lectures 10-14    [PPT, PDF]
Lectures 15-20    [PPT, PDF]

Lecture notes from Fall 2009
Lecture 14            [PPT, PDF]
Bloch sphere, general quantum operations in Krauss form, POVMs
Lecture 15            [PPT, PDF]
Stinespring vs. Krauss, separable states, trace distance
Lectures 1
6-17    [PPT, PDF] Holevo-Helstrom Theorem, entropy, compression
Lecture 18            [PPT, PDF] Grover's algorithm & lower bound for searching
Lecture 19            [PPT, PDF] Nonlocality (GHZ and CHSH)
Lectures 20-21    [PPT, PDF] Quantum error-correcting codes
Lectures 22-23    [PPT, PDF] Fault-tolerance (brief); BB84 quantum key distribution; Schmidt decomposition
Lecture 24            [PPT, PDF] Lo-Chau quantum key distribution protocol and its security

Projects (worth 40% of the final grade)
Each project consists of a written component and an oral presentation to the class.
It should explain and analyze some topic in quantum information processing, selected with the approval of the instructor. Your presentation should be about 30 minutes in length and your written component is not required to be of any particular length, but around 10 pages would be typical (PDF, PS, and Word are acceptable formats). You should explain the topic in your own words, at a level accessible to your classmates.

Partial list of possible project topics
[ PDF format, Word format ]
Note that you are welcome to pursue a project topic that is not on the list. In any event, you should seek approval from the instructor for your project topic.

References
An Introduction to Quantum Computation, P. Kaye, R. Laflamme, M. Mosca (Oxford University Press, 2007). Primary reference.
Quantum Computation and Quantum Information, Michael A. Nielsen and Isaac L. Chuang (Cambridge University Press, 2000). Secondary reference.