In the summer semester 2025 I am teaching quantum complexity theory at Saarland University. Here, I provide course material such as lecture notes and exercise sheets.
In the summer semester 2025 I am teaching quantum complexity theory at Saarland University. Here, I provide course material such as lecture notes and exercise sheets.
When and where:
Tue 2pm-4pm and Thu 12am-14pm in building E2 4, room SR10. The first lecture takes place April 8.
Students of informatics/computer science that successfully took the course "quantum complexity" in the past cannot also obtain credits for this course!
Course description:
Computational complexity has played a key role in shaping modern quantum computing. In this lecture at the interface of mathematics and computer science, we will explore quantum complexity classes such as Bounded Quantum Polynomial-Time (BQP) and Quantum Merlin-Arthur (QMA) and how they help us understand the fundamental limitations of quantum computers. We will study verification with interacting provers and, finally, we will examine how complexity-theoretic considerations have influenced recent quantum supremacy experiments.
Some literature:
Sevag Gharibian's lecture notes.
Scott Aaronson's lecture notes.
Nielsen and Chuang is arguably the standard reference for quantum computing.
Quantum computational complexity by John Watrous.
Quantum Hamiltonian Complexity survey by Gharibian, Huang, Landau, and Shin.
Exercise sheets:
Lecture notes:
The lecture notes are still under construction, so I am leaving some of the handwritten notes here for now:
Reading list for the exam:
The (unfortunately still incomplete) lecture notes contain the basics of the quantum computing formalism. Many of the same topics can be found in the first chapters of Nielsen & Chuang.
The CHSH game.
We used section 4, 5, and 6 of Sevag Gharibian's notes. We did not cover the proof of strong error reduction for QMA in the lecture.
We covered the definitions of various variants of QMA. A great read for this is the following survey article.
Some general takeaway messages of the exercise sheets might be asked. E.g. "Can you name an NP-complete variant of the local Hamiltonian problem? If I additionally allow single-qubit rotations of the local Hamiltonians, does the complexity of the problem change?"
The exam will not cover the last three lectures on interactions with quantum devices. The only exception might be aspects of the high-level question: What is a qubit? In the last three lectures we used parts of section 1, 2, and 5 (and a little of 8 and 9) of Thomas Vidick's notes.
Let me know if you have any questions about the material via email!