COMP-598: Quantum
Computation
Winter 2010
Lecture topics and suggested
readings
Lecture
1 (5 January):
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 (7 January):
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 (12 January):
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 (14 January):
Definition
of BQP
BQP
in PSPACE
Universality
Read
N & C 4.4, 4.5 (can skim universality proofs)
Lecture 5 (21 January):
Solovay-Kitaev theorem
Deutsch-Jozsa problem
Read
N & C 1.4.4 and pgs 617-618 (skim the rest of Appendix 3 if you’re
interested)
Lecture 6 (26 January –
Mark Wilde):
Reversible
classical computation
Read
N &C 3.2.5
Lecture 7 (28 January):
Simon’s
problem
Lecture 8 (2 February):
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 9 (4 February):
Phase
estimation
Read
N & C 5.2
Lecture 10 (9 February):
Order
finding and factoring
Read
N & C 5.3
Lecture
11 (11 February):
Finish
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.
The
hidden subgroup problem: Read N & C 5.4.3.
Lecture
12 (16 February):
Discrete
log
Graph
isomorphism as hidden subgroup
Read
N & C 5.4.2
Lecture
13 (18 February):
Grover
search
Amplitude
amplification
Read
N & C 6.1
Lecture
14 (2 March):
Collision
problem
Quantum
counting
Read
N & C 6.3
Lecture
15 (4 March):
Markov
chains
Definition
of hitting time
Lecture
16 (9 March):
Formula
for hitting time
Hitting
time on hypercube
Definition
of coined quantum walk
Lecture
17 (11 March):
Szegedy-style quantum walk
Analysis
of hitting time: square-root speed-up
Lecture
18 (16 March):
Element
distinctness by quantum walk
Lecture
19 (18 March):
Intro
to quantum error correction
9-qubit
code
Read
N & C 10.1 and 10.2
Lecture
20 (23 March):
Conditions
for quantum error correction
Stabilizer
codes (Shor, Steane,
5-qubit)
Read
N & C 10.3, 10.3.1, 10.5, 10.5.1,10.5.6 (can omit all discussion of check
matrices)
Lecture
21 (25 March):
Open
quantum systems as source of nonunitary errors
(This
is described at great length in N & C 2.4, 8.2 and 8.3)
Error
correction in stabilizer codes
Read
N & C 10.5.2, 10.5.5
Lecture
22 (30 March):
Logical
states: definition and preparation
Logical
operations: Z, X, Hadamard, Phase, CNOT
Transversality and fault-tolerance
Read
N & C 10.5.8, 10.6.2