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

Instructor: Richard Cleve

Email: cleve@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:

Christopher Chamberland (c6chambe@uwaterloo.ca)

office hours: Mondays 3:30-4:30pm, room QNC 4317 (or by appointment)

Abel Molina (abelmolinauw@gmail.com)

office hours: Wednesdays 4:30-5:30pm, room QNC 2212 (or by appointment)

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

Announcements

Projects:

- Current schedule of presentations is here: [pdf] (Version: Dec 16, 11:00am)
- If you used slides then please email instructor a copy (of the version of the slides that you used) to assist with the grading process.
- Please email instructor a copy of your written component within 5 non-weekend days of your presentation (extensions, within reason, to this 5-day guideline will probably be allowed).

*at most*(1+<μ|Φ+>)/2.

• (11/18) Assignment 5 has now been posted.

• (11/16) The solutions to Assignment 2 [pdf]

• (11/15) Added session times and rooms to schedule of presentations: [pdf] (Nov 17, 4pm)

• (11/4) The solutions to Assignment 2 [pdf]

• (11/3) Assignment 4 has now been posted.

• (10/19) Assignment 3 due date changed to Nov 1.

• (10/14) Uploaded more polished version of Assig. 3 (only small changes in wording & formatting)

• (10/13) Assignment 3 posted (due October 27, in class)

• (10/07) The solutions to Assignment 1 [pdf]

• (10/06) Projects choices due October 27; please see [pdf] and list of potential projects [pdf]

• (10/05) Assignment 2: correction to Q5(a), to the phases in the resulting state

• (10/03) Assignment 2 due date changed to October 13

• (10/03) Assignment 2: reworded parts of Q5 for clarity (but the questions have not changed)

• (10/03) No class on October 11, due to Mid-Term Study Break

• (09/29) Assignment 2 updated with question 5 now included

• (09/22) Please check the grading policy information page, right below where assignments are posted

• (09/13) Assignment 1 posted (due September 27, in class)

• (09/08) First class on September 8 (today!) at 2:30-3:50pm, in QNC 1201

• (09/20) Classical lower bound for Simon’s problem is here [pdf]

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 (due September 27, in class)

• Assignment 2 (due October 13, in class)

• Assignment 3 (due November 1, in class)

• Assignment 4 (due November 17, in class)

• Assignment 5 (due December 1, in class)

Grading policy information [html]

Lecture slides (for 2016)

- 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.
- Lecture 9 [ppt,pdf] Order-finding problem. Factoring problem.
- Lectures 10-12 [ppt,pdf] Density matrices. Bloch sphere, general quantum operations (including the partial trace), conversions between Krauss and Stinespring form.
- Lectures 13-14 [ppt,pdf] Nonlocality (GHZ and CHSH). The trace norm and the Holevo-Helstrom Theorem.
- Lecture 15 [ppt,pdf] Classical error-correcting codes, quantum error-correcting codes, including 9-qubit code and CSS codes, brief remarks about fault tolerant computing.
- Lecture 16 [ppt,pdf] Classical and quantum entropy. Classical and quantum compression.
- Lecture 17-18 [ppt,pdf] Grover’s search algorithm and lower bound for searching.
- Lectures 19-20 [ppt,pdf] Quantum key distribution, BB84 protocol, Lo-Chau protocol.
- Lecture 21 [ppt,pdf] Schmidt decomposition. Bit-commitment. Separable vs. entangled states (very briefly). Continuous-time evolution (very briefly).
- Lectures 22-23 [ppt,pdf] Communication complexity.

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 list of project topics to choose from [pdf]. You are also be welcome to pursue a project topic that is not on the list.

Here is a project sign-up sheet for indicating your project topic and indicating your time preferences [pdf].