Date  Topic  Supplements  

Mon  Jan 8  Intro to query complexity: notes  sec. 1,3 of survey 
Wed  Jan 10  Intro to query complexity  sec. 2,3 of Assadi notes, sec. 3.3 of survey 
Fri  Jan 12  Homework 1 posted: pdf  
Mon  Jan 15  Grover's algorithm: notes  
Wed  Jan 17  Class cancelled: inclement weather  
Mon  Jan 22  Basic design principles: notes  see references in notes 
Wed  Jan 24  Time and query complexity: notes  see references in notes 
Mon  Jan 29  kSAT and SETH; collision  classicaltoquantum circuit conversion, Beame notes 
Wed  Jan 31  directedSTCON in hypercube  paper 
Mon  Feb 5  Simon's problem: quantum upper bound  exploring Simon's algorithm with Daniel Simon 
Wed  Feb 7  Simon's problem: classical lower bound: notes  de Wolf notes 
Mon  Feb 12  Period finding in Z: notes  sec. 3.3 of Jozsa notes, Shor's story 
Mon  Feb 12  Homework 2 posted: pdf  
Mon  Feb 14  Period finding in Z and factoring  sec. 3.3 of Jozsa notes, Shor's story 
Mon  Feb 19  No class: midterm break  
Wed  Feb 21  No class: midterm break  
Mon  Feb 26  Factoring  sec. 3.3 of Jozsa notes, sec. 5.1 of Montanaro notes 
Wed  Feb 28  HSP: definitions, mixed quantum states  ch. 10 of [AMC] 
This is a graduatelevel topics course in quantum computation but assumes no prior knowledge of quantum information. The main focus will be on quantum algorithms and introducing open research problems.
Tentative list of topics:
Prior knowledge of quantum information is not a prerequisite. The main prerequisites are linear algebra (e.g., MATH 223, MATH 307, or CPSC 302) and mathematical maturity (e.g., from taking a thirdyear math course). Some prior knowledge of probability, group theory, analysis of algorithms, discrete math, optimization, or quantum mechanics is helpful but could also be picked up during the course.
The primary reference for this course is a set of excellent lecture notes on quantum algorithms by Andrew Childs: [AMC].
