COMP-598: Quantum
Computation
Fall 2011
Lecture topics and suggested
readings
Lecture
1 (1 September):
Course introduction
Deutsch’s problem
Read N & C: 1.1-1.3 (can omit
1.3.7) plus 1.4.1, 1.4.2, 1.4.3.
Lecture
2 (6 September):
Intro to quantum mechanics
Uncertainty principle
Read N & C:
Linear algebra review: 2.1 (can
omit 2.1.10)
Postulates of quantum mechanics:
2.2 (can omit 2.2.3, 2.2.4, 2.2.6 and section of 2.28 following exercise 2.66)
Lecture
3 (8 September):
More quantum mechanics
1- and 2- qubit gates
Read N & C:
Pages 171-178
If you aren’t familiar with
basic computer science, spend some time with chapter 3
Lecture 4 (13 September):
Definition
of BQP
BQP
in PSPACE
Universality
& the Solovay-Kitaev Theorem
Read
N & C 4.4, 4.5 (can skim universality proofs)
Read
N & C pgs 617-618 (skim the rest of Appendix 3 if you’re interested)
Lecture 5 (15 September):
Deutsch-Jozsa
problem
Simon’s
problem
Read
N & C 1.4.4
Lecture 6 (20 September):
Finish
Simon’s problem
Start
on the Fourier transform: read N & C 5.1
For
a different perspective, read Cormen, Rivest, Leiserson & Stein chapter 30.
The
book is available free
online for McGill students
Lecture 7 (22 September):
Implementing
the Fourier transform on a quantum computer
Phase
estimation: read N & C 5.2
Lecture 8 (25 September):
Order finding
Read N & C 5.3.1
Lecture
9 (27 September):
Finish order finding
Factoring
Read N & C 5.3
Details on reduction from order
finding to factoring and continued fractions
can be found in N & C Appendix A4.3 A4.4.
Lecture
10 (4 October):
The hidden subgroup problem: Read N
& C 5.4.3.
Discrete log
Graph isomorphism as hidden subgroup
Read N & C 5.4.2
Lecture
11 (6 October):
Grover search
Amplitude amplification
Read N & C 6.1
Lecture
12 (11 October):
Collision problem
Quantum counting
Read N & C 6.3