Lecture Quantum Complexity Theory (Summer 2025)
Organisation
- Lecturer: Prof. Dr. Markus Lohrey (Room H-A 7103, Tel. 0271-740-2826)
- Lecture: Monday 8:15-9:45 in H-B 6414
- Tutorials: Monday 10:15-11:45 in H-B 6414 (Start: April 28, 2025)
- Tutorials take place in even weeks and are supervised by Alexander Thumm.
Important Information
Please register for the coursework achievement in Quantum Complexity Theory (4INFMA313-S). Without the coursework achievement you cannot attend the exam. In order to pass the coursework achievement you have to successfully present at least one of the exercises from the exercise sheets on the black board in your tutorial class during the semester.
Some topics
- Basics on classical complexity theory
- Basics on quantum computing
- The complexity class BQP
- The complexity class QMA
- Local Hamiltonian problem
- Quick overview on interactive quantum complexity classes
Slides
(current version from April 6, 2025)
Exercises
Literature
- Classical complexity theory: Sanjeev Arora und Boaz Barak, Complexity Theory: A Modern Approach. Cambridge University Press 2009
- Quantum Computing: Michael Nielsen and Isaac Chuang, Quantum Information and Quantum Computing. Cambridge University Press 2016
- A good exposition of the Solovay-Kitaev Theorem is: Dawson, Nielsen, The Solovay-Kitaev Algorithm
- So far, there is no book on quantum complexity theory.
Here are some good sources:
- Lecture Introduction to Quantum Complexity Theory by Sevag Gharibian at University of Paderborn
- John Watrous, Quantum Computational Complexity (a survey on the field)
- Dorit Aharonov, Tomer Naveh, Quantum NP - A Survey (good exposition of the QMA-completeness of the local Hamiltonian problem)