Warum müssen QMA-Komplettprobleme Versprechen sein?

10

Ich lese Watrous 'exzellentes Umfragepapier auf Papier zur Theorie der Quantenkomplexität. Darin stellt er fest, dass es überraschend wäre, wenn ein QMA-vollständiges Problem ein leeres Versprechen hätte (dh eine Sprache sein). Warum ist das so?

Hat es damit zu tun, dass das k-lokale Hamilton-Problem ein Versprechen ist?

Dies führt mich auch zu einer verwandten Frage: Gibt es QMA-vollständige Probleme, die nicht von Natur aus "Quanten" sind?

cc.complexity-theory quantum-computing Henry Yuen
quelle
3
Ich denke, das wäre eine interessante Sache, da QMA als semantische Klasse definiert ist. Ein solch vollständiges Problem würde eine syntaktische Charakterisierung ergeben. Überprüfen Sie die zugehörigen Fragen zu syntaktischen / semantischen Komplexitätsklassen in cstheory / Mathoverflow.
Kaveh
3
Darüber hinaus ist dieses Phänomen nicht spezifisch für QMA. Andere semantisch definierte Klassen wie MA sind BPP. Es ist auch nicht bekannt, dass sie vollständige Sprachen haben.
Robin Kothari
1
Ich frage mich, welche notwendigen und ausreichenden Bedingungen in der Praxis gegeben sind, damit ein Problem "nicht quanten" ist. Ich nehme an, dass jedes Problem, das eine vollständig positive Karte ( z. B. ist eine gegebene CP-Karte invertierbar oder weit davon entfernt, invertierbar zu sein?) Oder eine Tensorproduktstruktur ( z. B. hat ein positiver semidefiniter Operator, der in einer k-lokalen Darstellung angegeben ist, Eigenwerte kleiner als hat Delta, oder sind sie alle wesentlich größer als Delta?) wären Beispiele für verdächtige Quantenprobleme, unabhängig davon, ob sie in Bezug auf Quantenkanäle / Evolution oder den Zustandsraum eines Aggregatsystems dargestellt werden oder nicht ...
Niel de Beaudrap

Antworten: