CO 781    Topics in Quantum Information

Ideas from Quantum in Classical Computation

University of Waterloo
Spring 2009

Lectures:    Tue, Thu    2:30  to  3:50  pm,    Room:    MC 4064
Office hours:    by appointment


Lecture Schedule Homework Suggested Reading / References


August 6: Links to the student projects are now up on the Projects page.

Past announcements available here.

Ashwin Nayak
C&O and IQC, U. Waterloo, and Perimeter Institute.
Contact information: here.


In this graduate level course, we will visit results in (classical) theoretical computer science that have benefited from ideas from quantum computation. Along the way, we will take a peek at the quantum origins of these ideas. Results of this nature include:

We will cover as many of these topics as possible; the choice of topics will be directed by the interest of the class participants.

Prerequisites: We assume knowledge of basic linear algebra, theoretical computer science. The material in a first course in quantum computation, such as CO 681, Introduction to Quantum Information Processing would be helpful. New concepts and results from quantum computing may be introduced along the way. Students are expected to show a fair bit of mathematical maturity.


The final mark in the course will be based on homeworks, and a term project. The weight given to the different components is

  1. Homework:     50%
  2. Term project and presentation:    50%
To take the class under the pass/not pass option, you are expected to attend the lectures and complete some of the graded components. You have the option to either submit two of the homeworks or to do the term project.


There will be three graded homework assignments. The homeworks will be posted here, and will be due generally after two--three weeks. Please drop off the homework as per the instructions therein.

Each assignment consists of several questions. You are expected to attempt all of them. You should be able to solve most of the problems in the homework on your own if you have understood the lectures. However you can expect an odd question that will require additional thought. You may work on the homework in small groups (and are encouraged to do so, in case of difficulty). You may also consult us. However, you should write up the solutions on your own and mention all sources of help.

Term project

This will consist of the creation of a Wikipedia page on a topic related to the course. In addition, you will be required to make a short presentation to the class. You may learn how to edit Wikipedia pages from their tutorial, and especially including math formulae from free online books. I also recommend that you review examples of good mathematical writing at the Wikipedia site. The deadline for the project is July 31, 2009. Please send the instructor the link to the page(s) you created by email.