Ein logischer Ansatz zur Quantenmechanik und Quantenkontextualität

• Antragsteller: Jonni Virtema, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2019 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 432788559

Kürzlich wurden Logiken mit probabilistischer Teamsemantik als ein vielversprechendes Mittel identifiziert, Eigenschaften und Phänomene in der Quantenmechanik zu modellieren. Das Anliegen dieses Projektes ist die Weiterführung und Analyse dieses Ansatzes. Eins der Projektziele ist es, Eigenschaften von Quantensystemen durch Logiken im selben Maße zu charakterisieren wie in der deskriptiven Komplexitätstheorie Komplexitätsklassen durch Formelklassen beschrieben werden. Insbesondere sind wir an der tiefgreifende Fragestellung interessiert, inwiefern wahrscheinlichkeitstheoretische Begriffe aus der Quantenmechanik sich auf ihre potentiellen Gegenstücke reduzieren.Logiken mit probabilistischer Teamsemantik besitzen eine inhärent Verbindung mit Komplexitätsklassen, welche auf Basis sogenannter Blum-Shub-Smale (BSS) Maschinen definiert sind. BSS-Maschinen können als Turingmaschinen gesehen werden, die als Eingaben reelle Zahlen erhalten und arithmetische Operationen auf diesen Zahlen in einem Zeitschritt durchführen. Grädel und Meer haben die Studie der deskriptiven Komplexität solcher Komplexitätstklassen initiiert. Sie zeigten, dass Varianten der existentiellen, zweistufigen Prädikatenlogik sowie der Fixpunkt-Logik, welche arithmetische Eigenschaften von reellen Zahlen ausdrücken können, genau die Analoge von NP und P im BSS-Modell erfassen.Ein spannendes Resultat von Durand et al. verbindet Logiken mit probabilistischer Teamsemantik zu mit den Logiken von Grädel und Meer sowie schließlich mit dem BSS-Berechnungsmodell. Hierdurch entsteht eine Brücke, die Eigenschaften von probabilistischen, verborgenen Variablen Modellen mit dem BSS-Maschinenmodell verbindet.Ein faszinierendes ungelöstes Problem ist die Fragestellung, ob Komplexitätsklassen auf Basis von BSS-Maschinen äquivalent zu entsprechenden Klassen auf Basis von Turingmaschinen sind, für den Fall, dass keine reelle Zahlen als Eingabewerte vorliegen. Wir planen Logiken auf Basis von probabilistischer Teamsemantik zu entwickeln, welche Komplexitätsklassen erfassen, die im BSS-Modell definiert sind. Diese logische Charakterisierungen sollen genutzt werden, um Kollapse oder Trennungen zugehörigen Klassen zu zeigen.Viele Entscheidungsprobleme im Bereich der verborgenen Variablen Modellen besitzen triviale obere Komplexitätsschranken im BSS-Rahmen. Solche Ergebnisse werden nichttriviale obere Schranken für die klassische Komplexität liefern (also bzgl. Berechnungen von Turingmaschinen). Unsere Arbeit an der deskriptiven Komplexität der Berechnungen auf reellen Zahlen kann auch möglicherweise Lösungen von sehr berühmten offenen Problemen liefern, wie zum Beispiel die Frage, ob die Komplexitätsklasse "exists R" mit NP zusammenfällt. Überdies wird das Projekt das Verständnis der BSS-Maschinenklassen und ihren Bezug zu traditionellen Komplexitätsklassen deutlich verbessern.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Großbritannien