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 July 15, 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)