Lecture Quantum Complexity Theory (Summer 2024)
Organisation
- Lecturer: Prof. Dr. Markus Lohrey (Room H-A 7103, Tel. 0271-740-2826)
- Lecture: Monday 8:00-10:00 in H-B 6414
- Tutorials: Monday 10:00-12:00 in H-B 6414 (Start: April 15, 2024)
- Tutorials take place in even weeks and are supervised by Julio Xochitemol.
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 21, 2024)
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)