Time:

Tuesday and Thursday from 8:30 to 10:00 (Winter 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. Other topics will 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 Online 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

Grading:

50% assignments, 50% presentations.

Lecture notes:

Scanned copies of my handwritten lecture notes.

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.

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