Was haben ein reisender Händler, das Packen eines Rucksacks und Seifenblasen auf einem Nagelbrett gemeinsam? Alle drei beschreiben Probleme, die auf klassischen Computern nur schwer zu lösen sind – doch was heißt „schwer“? In der Informatik werden solche Probleme und ihre Lösbarkeit mit Hilfe der Komplexitätstheorie beschrieben. Die Teilnehmenden lernen die verschiedenen Problemklassen sowie deren Zusammenhänge kennen und analysieren, welche Grenzen sich daraus für ihre praktische Berechenbarkeit ergeben.

Jedoch werden Berechnungen auf physikalischen Systemen (Computern) ausgeführt, deren Verhalten durch physikalische Gesetze bestimmt wird. Dort lassen sich wiederum sogenannte Quanteneffekte beobachten, durch die schwere Probleme scheinbar einfach gelöst werden. Wie also hängen diese Beobachtungen mit der Komplexitätstheorie zusammen?

Um diese Frage zu beantworten, taucht der Kurs in die Welt der Quantenphysik ein und lernt den Quantencomputer kennen. Um ein Verständnis dafür zu entwickeln, welche Probleme/Problemklassen ein Quantencomputer lösen kann, erarbeiten sich die Teilnehmenden einen der bekanntesten Quantenalgorithmen: den Grover-Algorithmus. Dadurch nähert sich der Kurs der Verbindung zwischen Physik und Komplexitätstheorie an, was weit hinein in die logischen Grundlagen der Physik und Informatik führt und letztlich tiefe philosophische Fragen aufwirft.

Da das Kursprogramm ehrgeizig ist, sollten Teilnehmende bereit sein, sich anhand eines Vorbereitungsskriptes in die Grundlagen von Logik und linearer Algebra einzuarbeiten. Trotz des mathematischen Schwerpunkts bleibt im Kurs jedoch auch Raum für philosophische Diskussionen.