Gibt es beschreibende Komplexitätsdarstellungen von Quantenkomplexitätsklassen?

Der Titel sagt mehr oder weniger alles, aber ich denke, ich könnte ein bisschen Hintergrundwissen und einige spezifische Beispiele hinzufügen, an denen ich interessiert bin.

Deskriptive Komplexitätstheoretiker wie Immerman und Fagin haben viele der bekanntesten Komplexitätsklassen mithilfe von Logik charakterisiert. Zum Beispiel kann NP mit existenziellen Abfragen zweiter Ordnung charakterisiert werden; P kann mit Abfragen erster Ordnung mit einem hinzugefügten Operator für den kleinsten Fixpunkt charakterisiert werden.

Meine Frage ist: Gab es Versuche, besonders erfolgreiche, solche Darstellungen für Quantenkomplexitätsklassen wie BQP oder NQP zu entwickeln? Wenn nein, warum nicht?

Vielen Dank.

Update (Moderator) : Diese Frage wird von diesem Beitrag auf mathoverflow vollständig beantwortet .

Ich denke, Robins Antwort auf meine Frage zu MO beantwortet auch diese Frage .

Eine deskriptive Komplexitätscharakterisierung einer Komplexitätsklasse ergibt eine Sprache, deren Abfragen (dh Formeln) genau die in C berechenbaren Funktionen sind . Die Syntax der Sprache ist normalerweise sehr einfach, dh wenn eine Zeichenfolge q angegeben wird , ist es einfach zu überprüfen, ob q eine wohlgeformte Abfrage der Sprache ist, zumindest wird erwartet, dass sie entscheidbar ist (aber normalerweise kann die Syntaxprüfung in a durchgeführt werden kleine Komplexitätsklasse). Dies würde eine effektive Aufzählung der Probleme in der Klasse C nach sich ziehen und eine syntaktische Charakterisierung für C liefern . (Wenn die Komplexität der Syntaxprüfung gering ist, kann dies auch bedeuten, dass ein vollständiges Problem für die Klasse vorliegt.)$C$$C$$q$$q$$C$$C$

In den Kommentaren oben, verbunden Robin zu Kord Eickmeyer und Martin Grohe Papier „ Randomisierung und Derandomization in Beschreibende Komplexitätstheorie “ , die eine „deskriptive Komplexität“ Charakterisierung gibt . Die Autoren selbst stellen in der Einleitung fest, dass sich dies von dem unterscheidet, was üblicherweise mit einer deskriptiven Komplexitätscharakterisierung gemeint ist:$BPP$

Wir beweisen, dass , die probabilistische Version der Festkommalogik mit Zählen, die Komplexitätsklasse B P P auch auf ungeordneten Strukturen erfasst . Für geordnete Strukturen ist dieses Ergebnis eine direkte Konsequenz des Immerman-Vardi-Theorems [7, 8], und für beliebige Strukturen folgt aus der Beobachtung, dass wir in BPIFP + C eine zufällige Reihenfolge mit hoher Wahrscheinlichkeit definieren können. Dennoch ist das Ergebnis auf den ersten Blick überraschend, weil es mit der offenen Frage, ob es eine logische Erfassung von P gibt , vergleichbar ist und weil angenommen wird, dass P = Die Einschränkung ist, dass die Logik B P ist$BPIFP+C$$BPP$$P$ .$P = BPP$ hat keine effektive Syntax und ist daher keine „Logik“ gemäß Gurevichs [9] Definition, die der Frage nach einer Logik, die P erfasst, zugrunde liegt. $BPIFP+C$$P$Wir glauben jedoch, dass eine völlig angemessene Beschreibung der Komplexitätsklasse B P P gibt , da die Definition von B P $BPIFP+C$$BPP$$BPP$ inhärent unwirksam ist (im Gegensatz zur Definition von in Bezug auf das Entscheidbare) Satz polynomisch getakteter Turingmaschinen).$P$

Ich bin kein Experte für finite Modelltheorie / deskriptive Komplexität (und würde gerne persönlich mehr von Experten hören), aber ich habe das Gefühl, dass es hier ein bisschen Betrug gibt, wenn ich sage, dass dies eine deskriptive Komplexitätscharakterisierung ist. Der Grund für mein Gefühl ist, dass wir, wenn wir eine nicht effektive Syntax haben dürfen, beliebige semantische Einschränkungen verwenden können, um die Klasse wohlgeformter Abfragen einzuschränken, und für jede Komplexitätsklasse eine "beschreibende Komplexitäts" -Charakterisierung geben können. Betrachten Sie beispielsweise (das P S p a c e erfasst ) und nehmen Sie dann genau die Abfragen an, die in B Q P berechenbar sind$SO(TC)$$PSpace$$BQP$ , oder die Sprache zu berücksichtigen , die für jede Maschine in einem Funktionssymbol hat $BQP$$BQP$

$\mathsf{P}$$\sigma$$\sigma$$\sigma$$M$$\varphi$$M$$\varphi$$\sigma$$R_1,R_2,\ldots$) This is a paraphrase of Definition 1.14 of this paper by Gurevich, which is reference [9] in the quote Kaveh gave.

The paper about BPP and randomized logic presents a significantly different framework. It starts with a finite vocabulary $\sigma$, and then considers a probability space of all vocabularies that extend $\sigma$ with some disjoint vocabulary $\rho$. So a formula is satisfiable in the new randomized logic if it is satisfiable in "enough" logics based on extensions of $\sigma$ by different $\rho$. This is my butchering of Definition 1 in the Eickmeyer-Grohe paper linked to by Robin Kothari. In particular, the vocabulary is not finite (well, each vocabulary is, but we have to consider infinitely many distinct vocabularies), the set of sentences of this logic is undecidable, and the notion of satisfiability is different from the one put forth by Gurevich.