Time:
Tuesday and Thursday from 8:30 to 10:00 (Fall 2011)

Room:
Arts 150

Instructor:     
Patrick Hayden

Teaching assistant:
Mark Wilde (Office hours 1 to 3 pm on Mondays in McConnell 104N)

Course description:
This course will present an introduction to quantum computation. Topics will include the quantum circuit model, searching unordered lists in sublinear time, Shor's polynomial time factoring algorithm, quantum walk algorithms, lower bound techniques and fault-tolerant 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
• Quantum error correction and fault tolerance
• Quantum complexity theory: QMA, PP, BQP, PostBQP, PH and other occupants of the complexity zoo
• Limits of quantum computation: Lower bound techniques
  • The polynomial method
  • The adversary method

Readings and lecture topics:
Here

Grading:
60% assignments, 40% 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).