Wenn P = BQP, bedeutet dies, dass PSPACE (= IP) = AM ist?

Kürzlich haben Watrous et al. Bewiesen, dass QIP (3) = PSPACE ein bemerkenswertes Ergebnis ist. Das war, gelinde gesagt, ein überraschendes Ergebnis für mich und hat mich zum Nachdenken angeregt ...

Ich fragte mich, was wäre, wenn Quantencomputer durch klassische Computer effizient simuliert werden könnten. Könnte dies EINFACH mit der Trennung zwischen IP und AM zusammenhängen? Was ich meine ist, dass IP durch die Polynomzahl der Runden der klassischen Interaktion charakterisiert ist, während AM 2 Runden der klassischen Interaktion hat. Könnte die Simulation eines Quantencomputers den Umfang der Interaktion für IP vom Polynom auf einen konstanten Wert reduzieren?

Gute Frage! Kurze Antwort: keine Implikation wie ist bekannt; aber das heißt nicht, dass es sich nicht lohnt zu beweisen ...

Ich würde jedoch sagen, dass es unwahrscheinlich ist, eine solche Implikation zu finden. Ich denke, die Botschaft der Viel-Quanten-Komplexitätstheorie ist, dass Quantencomputer zwar kein Allzweck-Allheilmittel zur Lösung schwerer Probleme sind, aber unter bestimmten Umständen viel leistungsfähiger als klassische Computer sein können.

Zum Beispiel können Quantenalgorithmen bei der Komplexität von Abfragen bestimmte Probleme effizient lösen, die klassische nachweislich nicht lösen können, wenn versprochen wird, dass die Eingabe einer netten globalen Struktur folgt. Shors Algorithmus basiert beispielsweise auf einem Algorithmus, mit dem die unbekannte Periode einer Funktion, deren Periodizität versprochen wurde, schnell gefunden werden kann. Andererseits sind Quantenabfragealgorithmen für die Lösung von Problemen, bei denen keine spezielle Struktur für die Eingabe angenommen wird, nicht zu viel stärker als klassische. (Siehe die Umfrage von Buhrman und de Wolf zur Komplexität von Abfragen zu diesem letzten Punkt.)

$\mathsf{QIP}(3) = \mathsf{QIP} = \mathsf{IP}$$\mathsf{P} = \mathsf{BQP}$

Ich stimme dem zu, was Andy geschrieben hat und ich wollte, dass diese "Antwort" ein Kommentar zu seiner Antwort ist, aber es ist offensichtlich zu lang für einen Kommentar ...

In jedem Fall kann es hilfreich sein, etwas mehr darüber zu sagen, welcher Aspekt der Quantenberechnung (oder möglicherweise der Quanteninformation) den Nachweis der PSPACE-Aufnahme in QIP (3) ermöglicht. Bekannte Beweise für diese Eingrenzung ergeben sich nicht aus der Fähigkeit des Verifizierers, Funktionen zu berechnen, die zufällig in der Zeit eines Quantenpolynoms berechenbar sind. Eine genauere Erklärung ist, dass die Beweise die spezifischen Möglichkeiten nutzen, mit denen ein Prüfer verwickelte Quantenzustände manipulieren kann, die er mit dem Prüfer teilt. Wenn der Prüfer nicht in der Lage wäre, Quanteninformationen zu manipulieren, oder wenn er auf magische Weise geteilte verschränkte Zustände stärker manipulieren könnte, als es die Quanteninformationstheorie zulässt, würden die Beweise nicht funktionieren.

Meiner Ansicht nach sagt der Einschluss von PSPACE in QIP (3) also nichts über die Beziehung zwischen AM und PSPACE aus.

Die Antworten von John Watrous und Andy Drucker sind hervorragend, um einige der damit verbundenen Probleme zu verstehen.

$P = BQP$$PH$$PSPACE \supseteq PH \supset\neq AM$

$IP = PSPACE$

[1] L. Fortnow und J. Rogers. Komplexitätsbeschränkungen bei der Quantenberechnung . Journal of Computer and System Sciences, 59 (2): 240-252, 1999. Sonderausgabe für ausgewählte Artikel der 13. IEEE-Konferenz zu Computational Complexity. Auch hier erhältlich .

Die anderen Antworten sind ausgezeichnet, und dies soll keines von ihnen ersetzen oder widersprechen, sondern lediglich eine Vorstellung davon vermitteln, warum P = BQP nicht notwendigerweise die Gleichheit zwischen quantalen und klassischen interaktiven Beweissystemen (für feste Runden usw.) impliziert. Wir wissen jetzt jedoch, dass QIP = IP dank der Arbeit von Jain, Ji, Upadhyay und Watrous, und ich versuche mit Sicherheit nicht zu behaupten, dass solche Gleichstellungen niemals vorkommen.

Wenn wir nur von P = BQP ausgehen, erfahren wir nur, welche Entscheidungsprobleme mit dem Quanten- und dem klassischen Modell beantwortet werden können. Dies bedeutet nicht, dass die Modelle tatsächlich gleich sind. Der Hauptunterschied besteht darin, dass Quantencomputer Zustände in Überlagerung verarbeiten können, was bedeutet, dass ihre Eingabe und Ausgabe nicht auf klassische Zustände beschränkt sein muss. Dies ist ein sehr wichtiger Unterschied zwischen Quanten- und klassischen Modellen, da die Quanteneingabe / -ausgabe es ermöglicht, Orakel mit Überlagerungen klassischer Zustände abzufragen oder Quantenzustände (die möglicherweise exponentielle klassische Beschreibungen aufweisen) zwischen einem Verifizierer und einem Prüfer zu kommunizieren. In der Tat gibt es Orakel, die BQP von P trennen, und die Quantenkommunikation führt bei einer Reihe von Problemen zu einer verringerten Kommunikationskomplexität. Somit,

Aus diesem Grund ist die Frage, ob P = BQP ist, nicht der entscheidende Faktor dafür, ob Quanten- und klassische Modelle in Situationen gleich sind, in denen Kommunikations- / Orakelabfragen verwendet werden.