QMA verstehen

Diese Frage ergibt sich aus einer Antwort, die Joe Fitzsimons auf eine andere Frage gab . Die meisten Klassen für natürliche Komplexität haben eine einzeilige "intuitive Beschreibung", mit deren Hilfe Kernprobleme in dieser Klasse charakterisiert werden können. Bei NP geht es um "effiziente Verifizierung", bei #P um "Aufzählen von Lösungen", bei PSPACE um "Spielen" und so weiter.

Ich habe MA allgemein als BP (NP) verstanden, wobei der M-Schritt Ihnen den NP-Guesser gibt und der A-Schritt der BP-Teil ist, und daher sind Fragen zur Beziehung zwischen MA und NP wirklich Derandomisierungsfragen. Meine Frage lautet also:

Gibt es eine natürliche Möglichkeit zu verstehen, was QMA erfasst?

cc.complexity-theory quantum-computing big-picture qma Suresh Venkat
quelle

Antworten:

Es ist im Wesentlichen dasselbe. QMA hat einen Quantenprüfer A, der Ihnen das begrenzte Fehlerbit plus die Fähigkeit gibt, Quantenzustände zu verarbeiten, und M gibt Ihnen die Fähigkeit, einen akzeptierenden Zustand nicht deterministisch auszuwählen, falls einer existiert.

Ein Quantenanalogon von MA ist jedoch viel natürlicher als NP, da jedes solche Analogon von NP erfordern würde, dass die Maschine in der Lage wäre, einen einzelnen Zustand aus einer unzähligen Anzahl möglicher Zustände nicht deterministisch zu schreiben. QMA erfordert nur endliche Wiedergabetreue, sodass Sie die Unendlichkeiten loswerden. In der Tat wird QMA oft als Quantenanalogon von NP behandelt (siehe zum Beispiel quant-ph / 0210077 ).

Joe Fitzsimons
quelle

x \in L

$x \in L$

x \notin L

$x \notin L$

Ja, Sie haben Recht, ich habe dort einen kleinen Fehler gemacht. Die nicht deterministische Sache wird jedoch etwas seltsam, da Sie einen Quantenzustand nicht deterministisch schreiben und wenn Sie einen Fehler von Null benötigen, bedeutet dies, dass Sie einen von unzähligen möglichen Zuständen schreiben. Dies scheint es schwierig zu machen, Ressourcen richtig zu berücksichtigen.

Joe Fitzsimons

netter Link zur Umfrage.

Suresh Venkat

@ Joe, @ Robin: Was ist, wenn Sie Ihren Nichtdeterminismus wie folgt einschränken? Wenn | x0> in der Berechnungsbasis gegeben ist, gibt ein "nichtdeterministisches Vermutungs" -Gatter entweder | x0> oder | x1> nichtdeterministisch aus (und natürlich nicht quantenweise). Ich glaube, dies gibt Ihnen die Klasse QCMA, die in dem Sinne, nach dem Robin fragt, einem Quantenanalogon von NP näher kommen könnte, aber ich bin mir nicht ganz sicher, ob ich etwas verpasst habe.

Joshua Grochow

Nun, es geht nur darum, ob Sie klassische oder Quantenbotschaften wollen. Die Ausgabe scheint nur für Quantenbotschaften zu entstehen.

Joe Fitzsimons

Die meisten untersuchten Quantenklassen (wie QMA, BQP, QIP und exotische wie QMIP und QRG) haben ein klassisches Gegenstück, und Sie erhalten die Quantenklasse, indem Sie quantitativ denken und Ihre Definition von "effizienter Berechnung" in "Polynomzeit auf a" ändern Quantencomputer. "

$NP \subseteq MA \subseteq QMA$

Der einfache Weg, eine Quantenklasse aus den meisten natürlichen klassischen Klassen herauszuholen, besteht darin, den Begriff der "effizienten Berechnung" von P oder BPP in BQP und den Begriff des Informationsaustauschs von Bits in Qubits zu ändern. So ist beispielsweise QIP dasselbe wie IP, wenn der BPP-Verifizierer zum BQP gemacht wird und die Kommunikation Qubits anstelle von Bits zulässt.

$x \in L$ $x \notin L$

Robin Kothari
quelle