Introduction to Quantum Information Processing
QIC 710, CS 768, C&O 681, PHYS 767, AM 871 Fall 2013

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
TAs:
Matthew Graydon (mgraydon@perimeterinstitute.ca)
office hours: Fridays 4:00-5:00pm, QNC 4401 (or by appointment)
Ansis Rosmanis (ansis.rosmanis@gmail.com)
office hours: Wednesdays 3:30-4:30pm, QNC 4114 (or by appointment)

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

Announcements
• (12/17) Wednesday, December 18 presentations will start at 9:30am (not 9:00am)
• (12/17) Revised schedule (Dec 17, Noon): [pdf]
• (11/25) Added new slides 23,24,25 to Lecture 22, to better explain bilateral CNOTS
• (11/12) Attached is presentation “scheduler” to indicate your preference/availability [txt,pdf]
• (11/12) Assignment 5 posted (due November 26, in class)
• (10/28) Assignment 5 posted (due November 26, in class)
• (10/28) Assignment 4 posted (due November 7, in class)
• (10/22) As announced in class, please send me an email (by Nov 1) with: (a) a tentative project title/topic; (b) a short description, with reference(s). (Please use subject “QIC 710 project” in the subject heading).
• (10/22) List of project topics has been updates with additional entries [pdf].
• (10/22) List of project topics has been updates with additional entries [pdf].
• (10/14) Preliminary list of project topics has been posted [pdf] (will be updated).
• (10/10) Assignment 3 posted (due October 24, in class)
• (09/26) Assignment 2 posted (due October 10, in class)
• (09/26) Proof of classical lower bound for Simon’s problem posted [pdf]
• (09/12) Assignment 1 posted (due September 26, in class)

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]

Lecture notes
  • 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 (beginning).
  • Lectures 6-8 [ppt,pdf] Simon’s problem (completion). 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. Introduction to eigenvalue estimation problem.
  • Lectures 9-11 [ppt,pdf] Review of eigenvalue estimation problem. Order-finding problem. Factoring problem. Density matrices. Bloch sphere, general quantum operations (including the partial trace).
  • Lectures 12-14 [ppt,pdf] Continuation of general quantum operations (including the partial trace). Conversions between Krauss and Stinespring form, separable states (very brief), trace norm, and the Holevo-Helstrom Theorem. Nonlocality (GHZ and CHSH).
  • Lectures 15-16 [ppt,pdf] Classical error-correcting codes, quantum error-correcting codes, including 9-qubit code and CSS codes, brief remarks about fault tolerant computing.
  • Lectures 17-18 [ppt,pdf] Classical and quantum entropy. Classical and quantum compression.
  • Lectures 19-20 [ppt,pdf] Grover’s search algorithm and lower bound for searching.
  • Lectures 21-22 [ppt,pdf] Quantum key distribution, BB84 protocol, Lo-Chau protocol.
  • Lecture 23 [ppt,pdf] Schmidt decomposition. Bit-commitment. Continuous-time evolution (very briefly).
  • Projects (worth 40% of 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. You should explain the topic in your own words, at a level accessible to your classmates.

Here is a preliminary list of project topics to choose from [pdf]. This will be updated in the next few days. You are also be welcome to pursue a project topic that is not on the list.