Tuesday and Thursday from 8:30 to 10:00 (Winter 2010)
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.
- 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:
60% assignments, 40% presentations.
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.
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).