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

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 introducing open research problems.

Tentative list of topics:

• Simon's problem: quantum upper bound, classical lower bound
• Factoring: Shor's algorithm, Regev's optimization
• Quantum walk and its applications to the element distinctness problem and glued-trees problem
• Quantum algorithms for algebraic problems like solving integer equations
• Quantum algorithms for simulating quantum systems
• Quantum algorithms for optimization: decoded quantum interferometry, gradient descent
• Quantum lower bound methods: polynomial, adversary, compressed oracle
• Classical simulation and dequantizing of quantum algorithms
• Quantum cryptography: key distribution, unforgeable money, post-quantum security

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 reference for this course is a set of excellent lecture notes on quantum algorithms by Andrew Childs: [AMC].