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

Course notes

Available here: cpsc536w_2023w2.pdf. Last updated: April 15th 2024.


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 17No class: 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
WedFeb 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]
MonMar 4HSP: query complexitych. 10 of [AMC]
WedMar 6HSP: query complexity; dihedral HSPch. 10, 13 of [AMC]
MonMar 11dihedral HSP; element distinctness (ED)ch. 13, ch. 19.1 of [AMC]
WedMar 13 amplitude amplification on ED; quantum walkch. 19.1, ch. 17.1-17.2 of [AMC]
MonMar 18quantum walkch. 17.3 of [AMC]
WedMar 20quantum walk, quantum phase estimationch. 17.4 of [AMC], sec. 6 of Montanaro notes
MonMar 25quantum walk for OR and ED ch. 18.1-18.2, ch. 19 of [AMC]
MonMar 25Homework 3 posted: pdf
WedMar 27adversary methodch. 22 of [AMC]
MonApr 1No class: Easter Monday
WedApr 3adversary method; divide and conquerch. 22 of [AMC]; paper
MonApr 8Hamiltonian simulation, block encoding, QSPsec. 6 of Jozsa notes, ch. 27 of [AMC]
WedApr 10QSPch. 27 of [AMC]
MonApr 15Homework 4 posted: pdf


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