QIC 710, CS 768, C&O 681, PHYS 767, AM 871 Fall 2015

Instructor: Richard Cleve

Email: cleve@cs.uwaterloo.ca (students: please include “QIC710” in subject, regardless of the version you’re in)

Office hours: after class or by appointment

Course web site: http://cleve.iqc.uwaterloo.ca/qic710.html

TAs:

Li Liu (l47liu@uwaterloo.ca)

office hours: Thursdays 11:00am-Noon, QNC 4101 (or by appointment)

Meenu Kumari (MKUMARI@uwaterloo.ca)

office hours: Wednesdays 10:00-11:00am, QNC 3117 (or by appointment)

Lectures: Tuesdays and Thursdays 2:30-3:50pm, in QNC 0101 (starting September 15)

Announcements

• 09/14: This page is still under construction. Last year’s page [pdf] has additional information.

Objectives

The objective of this course is to introduce the mathematical theory of quantum information processing (a.k.a. quantum computing) at the graduate level. Topics include: basic quantum algorithms (including Shor’s factoring algorithm and Grover’s search algorithm), complexity theory, density matrices and quantum operations on them, distance measures between quantum states, entropy and noiseless coding, error-correcting codes and fault-tolerance, non-locality, and cryptography.

• Additional details [html]

• Syllabus [pdf]

Assignments (5 assignments, worth 12% each):

• Assignment 1 [pdf] (to be inserted)

Grading policy information [html]

Lecture slides (from 2014)

- Lectures 1-3 [ppt,pdf] Introduction to the quantum information framework, quantum states, unitary operations measurements, quantum circuits, superdense coding, teleportation, no-cloning theorem, simulations between classical and quantum circuits, complexity classes.
- Lectures 4-5 [ppt,pdf] query scenario, Deutsch’s problem, one-out-of-four search, constant-vs-balanced problem, Simon’s problem.
- Lectures 6-8 [ppt,pdf] Discrete log problem and its reduction to Simon’s problem mod m. Simulating classically-defined black boxes. QFT mod m. Algorithm for Simon’s problem mod m. Computing QFT mod powers of 2. The eigenvalue estimation problem.
- Lectures 9-10 [ppt,pdf] Order-finding problem. Factoring problem.
- Lectures 11-13 [ppt,pdf] Density matrices. Bloch sphere, general quantum operations (including the partial trace), conversions between Krauss and Stinespring form.
- Lectures 14-15* [ppt,pdf] Nonlocality (GHZ and CHSH). The trace norm and the Holevo-Helstrom Theorem [* actually, we’re now one lecture ahead with respect to this numbering]
- Lectures 16-17 [ppt,pdf] Classical error-correcting codes, quantum error-correcting codes, including 9-qubit code and CSS codes, brief remarks about fault tolerant computing.
- Lecture 18 [ppt,pdf] Classical and quantum entropy. Classical and quantum compression.
- Lecture 19 [ppt,pdf] Grover’s search algorithm and lower bound for searching.
- Lectures 20-21 [ppt,pdf] Quantum key distribution, BB84 protocol, Lo-Chau protocol.
- Lecture 22 [ppt,pdf] Schmidt decomposition. Bit-commitment. Continuous-time evolution (very briefly).
- Lecture 23 [ppt,pdf] Separable vs. entangled states (very briefly). Continuous-time evolution (very briefly). Communication complexity.

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. You should explain the topic in your own words, at a level accessible to your classmates.

Here is a list of project topics to choose from [pdf]. You are also be welcome to pursue a project topic that is not on the list.