Lecture "Quantum Complexity Theory" (summer term 2026)
Lecturer: Norbert Schuch
u:find entry: 250053 VO Quantum Complexity Theory (2026S)
Overview
Quantum complexity theory studies the fundamental capabilities and limitations of quantum computers. Which problems can be solved efficiently with quantum resources? How do quantum computers compare to their classical counterparts? And how hard is it to determine properties of quantum many-body systems? Quantum complexity theory thus bridges quantum physics and theoretical computer science, revealing deep connections between computational hardness and physical phenomena. Central concepts covered in the course include complexity classes like BQP (problems efficiently solvable by quantum computers) and QMA (problems verifiable with quantum proofs), as well as complete problems that capture the full difficulty of these classes.
A central result discussed will be Kitaev's theorem, which establishes that the Local Hamiltonian problem — determining whether the ground state energy of a quantum system lies below a certain threshold — is QMA-complete. This is the quantum analogue of the classical concept of NP-complete problems (and specifically of the NP-completeness of 3-SAT), and reveals that finding ground state properties of quantum many-body systems is a hard problem even for quantum computers. This connection between complexity theory and condensed matter physics will be a recurring theme throughout the course.
Topics covered include: classical complexity foundations (P, NP, PSPACE), the quantum complexity landscape, Hamiltonian complexity and its connections to many-body physics, quantum interactive proofs, verification of quantum computations, and quantum computational supremacy.
Prerequisites
Basic familiarity with quantum computing (qubits, gates, the circuit model, ideally basic algorithms). No prior complexity theory background is required.
Literature
Classical Complexity Theory
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (especially Chapters 1-4, 6, 7, and 17). Availability: Draft on the authors' website, or book through the publisher (free access with UNIVIE login).
Quantum Complexity Theory
Organisatorial issues
For lecture times and locations, please check the u:find entry.
The exam will be an oral exam of 20 minutes. Further details will be communicated well in advance.