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

            Simonís original article

 

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

            Shorís original article

            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