CPSC 436Q: Quantum Computation (2024W1)

Instructor: Daochen Wang: wdaochen@cs.ubc.ca
TAs: Yabing Qi: yabingqi@student.ubc.ca, Xingyu Zhou: zxingyu@cs.ubc.ca
Term: 2024 Winter Term 1 (September 3rd 2024 to December 6th 2024)
Logistics: Monday and Wednesday, 12:30pm - 2:00pm, SPPH Room B151 (Floor B1)
Office hours: Assessment: 3 homework assignments (40%), 1 project (30%), 1 final exam (30%)
Discussion: Piazza

Schedule

Italicized entries are tentative.

DateTopicSupplements
WedSept 4intro to quantum computing: notes
MonSept 9intro to quantum computing: notes
WedSept 11CHSH game, Dirac notation, measurementend of lecture 2
FriSept 13Homework 1 released (due Sept 27): pdf, Latex
MonSept 16add/drop deadline
MonSept 16CHSH game: quantum analysis: notesO'Donnell video, article
WedSept 18CHSH game: Tsirelson's inequalityWilde notes (see 2.0.3)
MonSept 23intro to query complexitylecture 1
WedSept 25intro to query complexity: notesAmbainis survey
FriSept 27Candidate project topics released: pdf, Latex (see Project section below)
MonSept 30No class: National Day for Truth and Reconciliation
WedOct 2Grover's algorithmlecture 3, original paper
MonOct 7Grover's algorithm, randomized query lower boundlectures 2 and 3
WedOct 9simulating randomized query algorithms: notes
FriOct 11Homework 2 released (due Oct 28): pdf, Latex
MonOct 14No class: Thanksgiving Day
WedOct 16principle of deferred measurement, ORn, the Turing model lecture 4
MonOct 21simulating classical algorithms/oracle instantiation: notes Watrous video (see >45:37)
WedOct 23quantum time complexity of kSAT: notes
MonOct 28Simon's problem (1): notes Simon's blog post
WedOct 30Simon's problem (2): notes
MonNov 4Simon's problem (3): randomized query lower bound lecture 9
WedNov 6period finding in Z lecture 10-11
MonNov 11No class: midterm break / Remembrance Day
MonNov 11Homework 3 released (due Nov 25): pdf, Latex
WedNov 13No class: midterm break
MonNov 18Shor's algorithm (1) lecture 12, [NC, Sec. 5.1]
WedNov 20Shor's algorithm (2) lectures 10-11 and 12, Shor's story
MonNov 25adversary method ch. 22.2 of [AMC]
WedNov 27intro to quantum error correction [NC, Sec. 10.1], ch. 9 of Montanaro notes
MonDec 2Shor's nine-qubit code [NC, Sec. 10.2], ch. 9 of Montanaro notes
Final exam after Dec 6

Overview

This is an advanced undergraduate introductory course to quantum computation but assumes no prior knowledge of quantum information.

Tentative list of topics:

Project

You will work in a team of 2-3 to write an expository paper on a topic of your choice from the quantum computation and information literature. You should submit a project proposal, a project progress report, and your completed paper. A list of candidate project topics, along with some commentary, will be released on Sept 27. (You will not be disadvantaged if you choose a topic outside this list.)

Dates and guidelines (adapted from here):

Both the partial draft and final paper should be written in Latex using this template without any formatting changes.

Prerequisites

Prior knowledge of quantum information is not a prerequisite. The prerequisites are both of (a) one of CPSC 203, CPSC 221, and (b) one of MATH 152, MATH 221, MATH 223. Some prior knowledge of probability, discrete math, or quantum mechanics is helpful but could also be picked up during the course.

Resources

We will follow (i) the classic textbook Quantum Computation and Quantum Information by Nielsen and Chuang, (ii) a set of excellent lecture notes on quantum algorithms by Andrew M. Childs: [AMC], and (iii) my lecture notes.

Recommended lecture videos: Ryan O'Donnell (perhaps most relevant), Umesh Vazirani, John Watrous.

Policies

Policies and Resources to Support Student Success. In particular, note the Academic Concession policy, which covers unanticipated events or circumstances such as illnesses. Late policy: late homework or project documents will not be accepted except in cases of Academic Concession. Final exam policy: 2.5 hour handwritten exam with no notes or calculators allowed.


Template from Danica Sutherland