Das Quanten-Erfüllbarkeitsproblem - Algorithmen und komplexitätstheoretische Schwierigkeit

Das Erfüllbarkeitsproblem (k-SAT) gilt in der theoretischen Informatik als das traditionell "schwere" Problem und ist deswegen seit Jahrzehnten mit theoretischen Ansätzen aus dem Bereich Algorithmen und Komplexität studiert worden. Die Generalisierung des k-SAT Problems in der Quanteninformatik wird als "Quantum SAT" (k-QSAT) bezeichnet, das physikalisch motiviert ist. So wie k-SAT "schwer" für klassische Computer ist, so ist k-QSAT schwer für Quantencomputer. Im Vergleich zu k-SAT ist jedoch relativ wenig über k-QSAT bekannt. In dem hier beantragten Projekt möchten wir deshalb die folgenden Fragestellungen erforschen:

(1) Wann ist 2-QSAT schwer für höher-dimensionale Quantensysteme?

(2) Ein möglicher Ansatz zur Lösung schwerer Probleme ist das Analysieren einfacher Sonderfälle des Problems. Deshalb möchten wir untersuchen, welche Sonderfälle von k-QSAT "einfach" und welche noch "schwer" zu lösen sind?

(3) Ein anderer etablierter Ansatz zur Lösung schwerer Probleme ist die Entwicklung von parametrisierten Algorithmen. Basierend auf eigenen Vorarbeiten des Antragstellers zu parametrisierten Algorithmen für k-QSAT beabsichtigen wir, den ersten vollständigen parametrisierten Algorithmus für k-QSAT zu entwickeln.

DFG-Verfahren Sachbeihilfen