Quantum Algorithms and Complexity
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.
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 algorithmsQuantum 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
List the objectives or learning goals
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%)
* As for the timelines for the assignment submissions: students
will be expected to submit questions/
observations on a weekly basbasis (i.e., Weeks 2-8), deliver
talks in Weeks 5-8, and submit their mini-project
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