Quantum Algorithms and Complexity
Principal lecturer: Dr Tom Gur
Taken by: MPhil ACS, Part III
Code: L130
Term: Michaelmas
Hours: 16 (8x1-hour lectures and 8x1-hour seminars)
Format: In-person lectures
Class limit: max. 16 students
Prerequisites: Mathematical maturity and familiarity with (classical) algorithms, (classical) complexity theory, and quantum computing.
Moodle, timetable
Aims
This module is a research-focused introduction to the theory of quantum computing. The aim is to prepare the students to conduct research in quantum algorithms and quantum complexity theory.
Syllabus
Topics will vary from year to year, based on developments in cutting edge research. Representative topics include:
Quantum algorithms:
- Quantum learning theory
- Quantum property testing
- Shadow tomography
- Quantum walks
- Quantum state/unitary synthesis.
- Structure vs randomness in quantum algorithms
Quantum complexity theory:
- The quantum PCP conjecture
- Entanglement and MIP
- State complexity, AdS/CFT, and quantum gravity
- Quantum locally testable codes
- Pseudorandom states and unitaries
- Quantum zero-knowledge proofs
Objectives
On completion of this module, students should:
- be familiar with contemporary quantum algorithms
- develop an understanding of the power and limitations of quantum computation
- conduct research in quantum algorithms and complexity theory
Assessment
- Mini research project (70%)
- Presentation (20%)
- Attendance and participation (10%)
Timelines for the assignment submissions:
- submit questions/observations on a weekly basis (i.e., Weeks 2-8)
- deliver talks in Weeks 5-8
- submit their mini-project at the end of term
Recommended reading material and resources
“Quantum Computing Since Democritus” by Scott Aaronson
“Introduction to Quantum Information Science” by Scott Aaronson
“Quantum Computing: Lecture Notes” by Ronald de Wolf
“Quantum Computation and Quantum Information” by Nielsen and Chuang