CO 781 Topics in Quantum Information

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
	Projects

Announcements

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

Past announcements available here.

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

Outline

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:

Data-structure lower bounds.

Exponential lower bound for locally decodable codes.

Substate theorem and its applications.

Complexity of Sqrt(n)-Approximate Closest vector problem.

Interactive proofs with advice.

Closure of PP under intersection.

Approximation of Boolean functions by low degree polynomials.

Fourier analysis of matrix valued functions.

Adversary bound for decision tree complexity.

Lower bounds on formula size.

A scaling algorithm for Edmonds' problem.

Cryptosystems based on worst-case hardness of lattice problems.

Efficient (classical) simulation of quantum systems.

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.

Evaluation

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

Homework: 50%
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.

Homework

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.