CPSC 536W: Topics in Quantum Computation (2024W2)
Instructor: Daochen Wang: wdaochen@cs.ubc.ca
Term: 2024 Winter Term 2 (January 6th 2025 to April 8th 2025)
Logistics: Monday and Wednesday, 9:30am - 11am,
MCLD-Floor 2-Room 2014
Office hour: Friday 2pm - 3pm, ICICS X553
Assessment: 2 homework assignments (40%) and 1 project (60%)
Schedule
| Date | Topic | Supplements |
|---|
| Mon | Jan 6 | intro to quantum computing | |
|---|
| Fri | Jan 17 | add/drop deadline | |
|---|
Overview
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 complexity theory, in particular, super-polynomial speedups or the lack thereof.
Tentative list of topics:
- CHSH game
- Query and Turing models of computation
- Simon's problem: quantum upper bound, classical lower bound
- Factoring: Shor's algorithm
- Hidden subgroup problem
- Glued-trees problem
- Ground state preparation problem
- Yamakawa-Zhandry problem
- Quantum lower bound methods: adversary method and recording query method
- No super-polynomial speedup for total Boolean functions
- OSSS inequality and the Aaronson-Ambainis conjecture
- Interesting papers that I read as the course progresses
Project
You will work in a team of 1-2 to write a paper on a topic of your choice from the quantum algorithms literature. In addition to reviewing previous work on your topic, you should aim to identify new research directions. You should submit a project proposal and a final paper, as well as give a talk on the topic. A list of candidate topics, along with some commentary, will be released on [TBC]. (You will not be disadvantaged if you choose a topic outside this list.)
Dates and guidelines (adapted from here):
- Proposal (worth 10%, due [TBC]): 1-2 pages summarizing the topic, a timeline, and a list of selected references.
- Final paper (worth 50%, due [TBC]): a paper covering your chosen topic. Original research is encouraged but not expected. Half of the marks will be for scientific content and the other half for presentation. The paper should be at most 10 pages in length excluding references.
- Talk (worth 40%, due [TBC]): a 30-minute talk on your project towards the end of the semester.
Both the proposal 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 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.
Resources
The primary references for this course are my lecture notes and a set of excellent lecture notes on quantum algorithms by Andrew M. Childs: [AMC].