Time:

Tuesday and Thursday from 4:00 to 5:30 (Fall 2007)

Room:

McConnell 320

Instructor:

Patrick Hayden

Course description:

This course will present an introduction to quantum computation. After introducing the quantum computing model, we will cover the basic quantum algorithms including Grover's search algorithm and Shor's RSA-busting factoring algorithm. Depending on the students' interests, significant time may also (or instead) be
devoted to quantum information theory. Other topics may include quantum complexity theory and, time-permitting, the basics of topological quantum computation.

The course will be mathematical, but quite elementary. Linear algebra and general mathematical maturity will be essential. Familiarity with quantum mechanics is not required. The material will be covered through a combination of lectures and student presentations.

** **Course outline:

- The quantum circuit model
- Quantum algorithms:
- Deutsch-Jozsa and Simon’s problem
- Grover search
- The quantum Fourier transform (factoring and discrete log)
- Hidden shift problems
- Quantum walk algorithms

- Limits of quantum computation: Lower bound techniques
- The polynomial method
- The adversary method

- Quantum complexity theory
- QMA, PP, BQP, PostBQP, PH and other occupants of the complexity zoo

- Quantum information theory: from Schumacher compression to the mother of all protocols

Grading:

50% assignments, 50% presentations.

Text:

There is no text for the course. However, much of the material can be found in Quantum Computation and Quantum Information by Nielsen and Chuang, which is an excellent introduction to the field as a whole. Several copies should be available in the university bookstore.

Presentations:

More information can be found here.

Assignments:

Coming soon...

Embarrassing obligatory inclusion:

By the direction of Senate (January 29, 2003), all course outlines have to include the following statement: McGill University values academic integrity. Therefore, all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/integrity for more information).