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  No class: 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  
Wed  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] 
Mon  Mar 4  HSP: query complexity  ch. 10 of [AMC] 
Wed  Mar 6  HSP: query complexity; dihedral HSP  ch. 10, 13 of [AMC] 
Mon  Mar 11  dihedral HSP; element distinctness (ED)  ch. 13, ch. 19.1 of [AMC] 
Wed  Mar 13  amplitude amplification on ED; quantum walk  ch. 19.1, ch. 17.117.2 of [AMC] 
Mon  Mar 18  quantum walk  ch. 17.3 of [AMC] 
Wed  Mar 20  quantum walk, quantum phase estimation  ch. 17.4 of [AMC], sec. 6 of Montanaro notes 
Mon  Mar 25  quantum walk for OR and ED  ch. 18.118.2, ch. 19 of [AMC] 
Mon  Mar 25  Homework 3 posted: pdf  
Wed  Mar 27  adversary method  ch. 22 of [AMC] 
Mon  Apr 1  No class: Easter Monday  
Wed  Apr 3  adversary method; divide and conquer  ch. 22 of [AMC]; paper 
Mon  Apr 8  Hamiltonian simulation, block encoding, QSP  sec. 6 of Jozsa notes, ch. 27 of [AMC] 
Wed  Apr 10  QSP  ch. 27 of [AMC] 
Mon  Apr 15  Homework 4 posted: pdf 
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].
