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

Instructor: Richard Cleve

Email: cleve@uwaterloo.ca (students: please include “QIC710” in subject, regardless of the version you’re in)
Office hours: after class in QNC 3129 or by appointment
TAs:


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

Lectures: Tuesdays and Thursdays 8:30-9:50am, in MC 2054 (starting September 5)

Announcements
• Schedule of presentations: [pdf] (last updated Dec 18, 4:00pm)
Note: titles have been lightly edited for space; please let me know if you want to change your title, or make any corrections.

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] (due September 19)
• Assignment 2 [pdf] (due October 3)
• Assignment 3 [pdf] (due October 24)
• Assignment 4 [pdf] (due November 7)
• Assignment 5 [pdf] (due November 21)

Grading policy information [html]

Lecture Notes/Slides

  • Lectures 1-3 [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 [pdf] Query scenario, Deutsch’s problem, one-out-of-four search, constant-vs-balanced problem, Simon’s problem.

  • Supplementary to lecture 5: [pdf] Proof of classical lower bound on query complexity of Simon's Problem.

  • Lectures 6-8 [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.

  • Lecture 9 [pdf] Order-finding problem. Factoring problem.

  • Lectures 10-11 [pdf] (Note: this topic was started out of order, on September 26) Density matrices. Bloch sphere, introduction to quantum channels.

  • Lecture 12 [pdf] Quantum channels (including the partial trace), conversions between Krauss and Stinespring form.

  • Lectures 13-14 [pdf] Nonlocality (GHZ and CHSH). The trace norm and the Holevo-Helstrom Theorem.

  • Lecture 15 [pdf] Classical error-correcting codes, quantum error-correcting codes, including 9-qubit code and CSS codes, brief remarks about fault tolerant computing.

  • Lecture 16 [pdf] Classical and quantum entropy. Classical and quantum data compression.

  • Lecture 17-18 [pdf] Grover’s search algorithm and lower bound for searching.

  • Lectures 19-20 [pdf] Quantum key distribution, BB84 protocol, Lo-Chau protocol.

  • Lecture 21 [pdf] Schmidt decomposition. Bit-commitment. Separable vs. entangled states (very briefly). Continuous-time evolution (very briefly).

  • Lectures 22-23 [pdf] Communication complexity.


Projects (worth 40% of grade)

  • Each project is 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. You should explain the topic in your own words, at a level accessible to your classmates.
  • Session preference form: [pdf] (please fill out and submit by October 31).
  • Updated 10/24 (with information about sessions): Procedural information about your project is here: [pdf].
  • Updated 10/24 (with a section on "quantum machine learning" at the end): 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.