Quantenbeweissysteme mit unverschränkten Beweisen (QPUP)

• Antragsteller: Professor Dr. Sevag Gharibian
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 572703436

Die Komplexitätsklasse NP hat eine grundlegende Rolle bei der Charakterisierung der inhärenten Schwierigkeit von Berechnungsproblemen gespielt. Konkret besteht NP aus allen Berechnungsproblemen mit einer JA- oder NEIN-Antwort, für die es, wenn die Antwort JA lautet, einen effizient überprüfbaren Beweis für diese Tatsache gibt. In der Quantenphysik hat die Quantenverallgemeinerung von NP eine ähnlich wichtige Rolle gespielt. In der kanonischen Definition von Quanten-NP, bekannt als Quantum Merlin-Arthur (QMA), ist der Beweis nun ein Quantenzustand und der Verifizierer ein Quantenschaltkreis polynominaler Größe. Über QMA ist heute viel bekannt, darunter auch Grenzen seiner Leistungsfähigkeit und die Tatsache, dass es die Komplexität der physikalisch motivierten Verallgemeinerung des Boole'schen Erfüllbarkeitsproblems, des lokalen Hamilton-Problems, erfasst. In der Quantenmechanik gibt es jedoch ein einzigartiges Quantenphänomen, das einem QMA-Beweissystem hinzugefügt werden kann: die „Unverschränkung“. Grob gesagt kann im Gegensatz zu klassischen Beweissystemen in der Quantenwelt ein n-Qubit-Zustand verschränkt sein, d. h. auf nicht-klassische Weise stark korreliert. Wir sagen, dass ein Quantenbeweissystem „unverschränkt“ ist, wenn der Beweiser verspricht, einen Zustand v auf 2n Qubits zu senden, von denen die ersten n (bzw. die letzten n) untereinander verschränkt sind, aber keine Verschränkung zwischen den ersten n Qubits und den letzten n Qubits besteht. Die resultierende Klasse ist als QMA(2) bekannt und gilt allgemein als stärker als QMA. Tatsächlich besitzt sie bemerkenswerte Eigenschaften, die für QMA nicht bekannt sind, wie beispielsweise die exponentielle Kompression klassischer Beweise. Die bekannten Grenzen der Macht von QMA(2) bleiben jedoch im Wesentlichen trivial, nämlich QMA (Untergrenze) und NEXP (Obergrenze). Dieser Förderantrag zielt darauf ab, die Macht von QMA(2) gründlich zu untersuchen. Konkret werden drei Richtungen verfolgt: (1) Klassische Beweiskompression, (2) Varianten von QMA(2) und (3) schärfere Grenzen für die Macht von QMA(2). Im ersten Teil wird ein tieferes Verständnis der Grenzen der Unverschränkung bei der Erfassung klassischer Beweissysteme erarbeitet – kann QMA(2) beispielsweise interaktive Beweise mit hin- und hergesendeten Nachrichten erfassen? Der zweite Teil untersucht, wie eine Variation der Definition von QMA(2), beispielsweise durch Einschränkung des Gate-Sets des Verifizierers oder Hinzufügen eines zusätzlichen universell quantifizierten Beweises, die Macht der Klasse verändert. Der dritte Teil zielt schließlich darauf ab, die bekannten unteren und oberen Grenzen für QMA(2) zu verbessern, indem beispielsweise gezeigt wird, dass QMA(2) die Komplexitätsklasse co-NP enthält.

• DFG-Verfahren: Sachbeihilfen