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