CPSC 536W: Topics in Quantum Computation (2023W2)

Instructor: Daochen Wang: wdaochen@cs.ubc.ca; TA: Xingyu Zhou: zxingyu@cs.ubc.ca
Term: 2023 Winter Term 2 (January 8th 2024 to April 12th 2024)
Logistics: Monday and Wednesday, 9:30am - 11am, Hugh Dempster Pavilion Room 101
Office hours: Friday 2pm - 3pm, ICICS X553; Wednesday 1pm - 2pm, ICICS X341
Assessment: 4 homework assignments
Registration: CS students use: CPSC 536W 201; Non-CS students use: CPSC 536W 2W1


MonJan 8Intro to query complexity: notessec. 1,3 of survey
WedJan 10Intro to query complexitysec. 2,3 of Assadi notes, sec. 3.3 of survey
FriJan 12Homework 1 posted: pdf
MonJan 15Grover's algorithm: notes
WedJan 17Class cancelled: inclement weather
MonJan 22Basic design principles: notessee references in notes
WedJan 24Time and query complexity: notessee references in notes
MonJan 29kSAT and SETH; collisionclassical-to-quantum circuit conversion, Beame notes
WedJan 31directed-STCON in hypercubepaper
MonFeb 5Simon's problem: quantum upper boundexploring Simon's algorithm with Daniel Simon
WedFeb 7Simon's problem: classical lower bound: notesde Wolf notes
MonFeb 12Period finding in Z: notessec. 3.3 of Jozsa notes, Shor's story
MonFeb 12Homework 2 posted: pdf
MonFeb 14Period finding in Z and factoringsec. 3.3 of Jozsa notes, Shor's story
MonFeb 19No class: mid-term break
WedFeb 21No class: mid-term break
MonFeb 26Factoringsec. 3.3 of Jozsa notes, sec. 5.1 of Montanaro notes
WedFeb 28HSP: definitions, mixed quantum states ch. 10 of [AMC]


This is a graduate-level 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 third-year 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].

Template from Danica Sutherland