Gibt es ein Quantenanalogon des VP vs. VNP-Problems?

Aus Wikipedia :

$\mathsf{VP}$ f K. : Die Klasse VP ist das algebraische Analogon von P; es ist die Klasse von Polynomen mit Polynomgrad, die Polynomgrößenschaltungen über ein festes Feld .$f$$K$

$\mathsf{VNP}$ f f : Die Klasse VNP ist das Analogon von NP. VNP kann als die Klasse von Polynomen mit Polynomgrad betrachtet werden, so dass wir bei gegebenem Monom seinen Koeffizienten in mit einer Schaltung mit Polynomgröße effizient bestimmen können .$f$$f$

Es gab Versuche, Polynome Verwendung von Quantenschaltungen zu implementieren , vgl. arXiv: 1805.12445 . es also ein Quantenanalogon für das vs. ? Gibt es ein Papier zu diesem Thema?$f$$\mathsf{VP}$$\mathsf{VNP}$

^{PS: Ich habe auf der Quantum Computing- Website eine sehr verwandte Frage gestellt .}

Dies ist keine richtige Antwort, aber einige Beobachtungen, die für einen Kommentar zu lang sind. Ich habe schon früher über diese Frage nachgedacht, aber da ich kein Quantenexperte bin, konnte ich sie nie wirklich lösen. Das, was Sie dafür wollen, ist ein Polynom (wirklich eine Familie von Polynomen , eines für jedes ), so dass in gewisser Weise für (bzw. ). Während es bei Polynomen viele Probleme gibt, die in Quantenklassen auftreten, haben sie typischerweise eher die Form "Berechnen Sie bei einem Eingabegraphen G (die Koeffizienten oder die Bewertung von) eines Polynoms an einem Punkt$f$$f_n$$n$$f = (f_n)$$\mathsf{BQP}$$\mathsf{QMA}$$f_G(x)$$x$". Zum Beispiel ist das Jones-Polynom eine natürliche Sache, an die man denken sollte. Wenn ein Link gegeben ist, ist die Annäherung seines Jones-Polynoms an einer Wurzel der Einheit -vollständig. Die Bewertung des Jones-Polynoms bei einem Link im Allgemeinen ist -hard (siehe Referenzen z . B. hier ). Daher gibt es hier zwei Probleme bei der Verwendung von " ": Das erste ist, dass das Jones-Polynom im Allgemeinen -hard, wenn Sie also versuchen, es zu verwenden, erhalten Sie möglicherweise erneut . Zweitens handelt es sich nicht nur um eine einzelne Familie von Polynomen, sondern um eine Frage der obigen Form (bei gegebenem Eingabeobjekt berechnen Sie$\mathsf{BQP}$$\mathsf{\# P}$V B Q P # P V N P G f G f n ( G )$\mathsf{VBQP}$$\mathsf{\# P}$$\mathsf{VNP}$$G$$f_G$, anstatt bewerten, was wir wollen würden).$f_n(G)$

Ein anderer Ansatz, den Sie versuchen könnten, besteht darin, die Amplituden des Ausgangs einer Quantenschaltung als Polynom in ihren Eingängen zu betrachten. Aber diese Amplituden können permanent sein, so dass wir wieder schnell auf die - oder stoßen.$\mathsf{\# P}$$\mathsf{VNP}$

Ein weiterer Ansatz, den Sie versuchen könnten, besteht darin, die "Universalschaltungs" für -vollständige Probleme irgendwie nachzuahmen (die von Burgisser und dann Raz , siehe z. B. Mahajans Umfrage oder die Referenzen in Abschnitt 5 von Mahajan-Saurabh ). mit universellen Quantenschaltungen. Hier stoßen wir auf das Problem, dass es eine gewisse Nichtübereinstimmung zwischen Quantenschaltungen und algebraischen Schaltungen zu geben scheint. Insbesondere behält eine Quantenschaltung auf n Qubits$\mathsf{VP}$2 n B Q P.$2^n$Amplituden, während eine algebraische Schaltung ein einzelnes Ringelement auf jedem Draht beibehält, also eine Gesamtzahl, die in der Größe der Schaltung polynomisch ist (linear, wenn Sie die Größe anhand der Anzahl der Drähte messen oder ein begrenztes Fan-In haben). Quantenschaltungen, die viel weniger Informationen als diese enthalten - z. B. Stabilisatorschaltungen oder Schaltungen mit linearer Optik - scheinen nicht die volle Leistung von zu erfassen .$\mathsf{BQP}$

In einem verwandten Hinweis sind , , und alle semantische Klassen ohne bekannte syntaktische Charakterisierung (siehe z. B. dies oder das ). Mein erster Instinkt ist, dass dies mit der Tatsache zusammenhängt, dass algebraische Komplexitätsklassen wie syntaktisch sind, aber ich bin mir nicht sicher, ob das richtig ist. Ich glaube jedenfalls nicht, dass wir eine solche semantische Klasse mit einem algebraischen Analogon kennen.$\mathsf{BPP}$$\mathsf{MA}$$\mathsf{BQP}$$\mathsf{QMA}$V P.$\mathsf{VP}$

Dies bedeutet nicht, dass all diese Ansätze nicht funktionieren können, nur um einige Gedanken darüber auszutauschen. Ich hoffe, jemand kann es zum Laufen bringen!