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

Schedule

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. Outstanding projects will also include some original research contributions. 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.

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].