Instructor:

Ashwin Nayak
Combinatorics and Optimization, U. Waterloo
and
Perimeter Institute for Theoretical Physics

Email:    anayak [at] math
Office:    MC 4034
Phone extension:    3601

Outline

This is a graduate level course, intended as a follow-up to CO 681, Introduction to Quantum Information Processing. It will cover a broad selection of advanced topics that will prepare students for research in the area. It will also include topics from the CO PhD comprehensive exam in quantum computation not covered in the introductory course. The main idea is to learn important techniques relevant to the field by visiting recent results.

Preliminary list of topics:

• Communication & Information theory: Efficient quantum protocols, Holevo and related bounds, Quantum error-correction.
• Cryptography: Unconditionally secure quantum key exchange, Impossibility of ideal bit-commitment, Quantum coin flipping.
• Algorithms: Quantum walks, Hidden subgroup in non-abelian groups.
• Lower bounds: Optimality of quantum search, Lower bound techniques.
• Computational Complexity: Quantum interactive proofs, Quantum proofs for hard problems.
• Impact on classical theoretical computer science: Locally decodable codes, Shortest lattice vector problem.

Prerequisites: I will assume knowledge of basic linear algebra. theoretical computer science, and the material in CO 681, the introductory class on quantum information. Students will be expected to show a fair bit of mathematical maturity.
 

Text

There is no prescribed text-book for the course. We will develop lecture notes as we go along. Relevant articles may be accessed by following the bibliography link above.
 

Evaluation

The final mark in the course will be based on the scribe notes you prepare, homework, and a term paper. The weight given to the different components is

1. Scribe notes:   10%
2. Homework:     40%
3. Term paper:    50%

Scribe notes

You will be required to take notes for two lectures of your choice. Preparing lecture notes will help you understand the lecture material more thoroughly, and give you another opportunity to think about the material.

Please use this Latex template, and the macros defined in it to typeset the notes. Notes for a Tuesday lecture will be due by the following Sunday, and those for Thursday will be due the following Tuesday. This will ensure that all the students have access to the notes before the homework based on these lectures is due.
 

Homework

There will be three graded homework assignments in all. There will be a homework assignment essentially every month. The homework will be posted on the web and will be due three weeks later. I will collect the homework in class the day they are due.

Each assignment will consist of four to five questions. You are required 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 me. However, you should write up the solutions on your own and mention all sources of help.

Term paper

This will consist of further reading on a topic of your choice. You will be required to make a short presentation to me and possibly to the rest of the class on it during the last class meeting (August 3). You will also be required to write a short report on your topic, which will be due on August 8 (by email).

Feedback

Please pass on your comments, criticism, and opinions on the course to me; these are always welcome. If you prefer not to reveal your identity, you could use an anonymous remailer, like this one, to send me email.