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

††††††††††† Simonís original article

††††††††††† 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

††††††††††† Shorís original article

††††††††††† 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