Ideas from Quantum in Classical Computation

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.

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%

**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.