Quanten-PCP und Simulationshärte von Hamiltonianern

8

Ich habe ein paar Fragen zur Quantum PCP-Vermutung:

  1. Was ist die Aussage der Quanten-PCP-Vermutung?

  2. Welche Implikationen hätte der Quanten-PCP-Satz für die Simulation von Hamiltonianern?

  3. Wird angenommen, dass die Übernahme von Irit Dinurs Beweis des klassischen PCP-Theorems wahrscheinlich zu einem Beweis der Quantum-PCP-Vermutung führt?

  4. Welchen Hintergrund wird benötigt, um Artikel über das Problem zu lesen?

Die Kopie der Frage zu MO

cc.complexity-theory quantum-computing approximation-hardness pcp physics Gemeinschaft
quelle
1
Verwandte Frage: Was sind gute Referenzen zum Verständnis des Beweises des PCP-Theorems?
Kaveh
12
Es gibt keinen Quanten-PCP-Satz. Die Leute versuchen es zu beweisen, aber ob ein solches Theorem existiert (und vielleicht genau wie es aussehen würde), ist eine der großen offenen Fragen im Quantencomputer.
Peter Shor
7
Noah Rahman: Bitte verlinken Sie beim Crossposting auf die ursprüngliche Frage. Andernfalls würde nicht jeder wissen, dass Sie bereits eine sehr gute Antwort von Peter Shor erhalten haben. mathoverflow.net/questions/45106/quantum-pcp-theorem
Tsuyoshi Ito
3
Ich wünschte, ich wüsste, was der beste Ansatz ist, um ein Quanten-PCP-Theorem zu beweisen oder zu widerlegen. Das Problem ist, wenn ich es gewusst hätte, hätte ich es bereits bewiesen oder widerlegt.
Tsuyoshi Ito
2
Entschuldigung, ich werde die Frage schließen. Mir wurde von jemandem gesagt, ich solle es hier posten. Aber um Robins Frage zu beantworten, hat meine Forschung mit der Anwendbarkeit dieser sogenannten DMRG-Algorithmen zu tun, und so bin ich auf die QPCP-Vermutung gestoßen (nachdem ich zuvor eine Seminarklasse über Kitaevs verschiedene QMA-vollständige Probleme vorgestellt hatte)

Antworten:

8

Wie Shor sagte, gibt es (noch!) Keinen QPCP-Satz. Eine Vermutung (nennen wir es die QPCP-Vermutung) lautet: Betrachten Sie einen Graphen von N Eckpunkten vom Grad O (1). Ordnen Sie jedem Scheitelpunkt ein Qudit mit der Hilbert-Raumdimension O (1) zu. Der Hamilton-Operator sei eine Summe von Termen für jede Kante, wobei jeder dieser Term nur auf die Qudits auf den Eckpunkten einwirkt, wobei die Operatornorm jedes solchen Terms durch O (1) begrenzt ist, so dass die Operatornorm des Hamilton-Operators O (N ist ). Dann wird vermutet, dass es ein Epsilon> 0 gibt, so dass es QMA-schwierig ist, die Grundzustandsenergie des Problems auf ein genaues Epsilon N zu approximieren.

Eine etwas stärkere Vermutung besteht darin, den Fall zu betrachten, in dem jeder solche Term, der auf eine Kante wirkt, ein Projektor ist, so dass die Grundzustandsenergie nicht negativ ist, und die Vermutung ist, dass es QMA-schwer ist, zu bestimmen, ob die Grundzustandsenergie ist 0 gegeben ein Versprechen, dass wenn es nicht Null ist, es mindestens epsilon N ist.

Es gibt auch andere Versionen der Vermutung, aber das sind zwei interessante mit der natürlichsten Beziehung zur Physik. Eine noch stärkere Vermutung (daher wahrscheinlich leichter zu widerlegen, wenn Sie glauben, dass diese Vermutungen falsch sind) besteht darin, den Fall zu betrachten, in dem der Hamilton-Operator eine Summe von Pendelprojektoren ist.

matte Hastings
quelle
6
Das klassische PCP-Theorem besagt, dass alle diese Fragen mindestens NP-schwer sind.
Peter Shor
6

Grundsätzlich wurde in dieser Umfrage von Dorit Aharonov, Itai Arad und Thomas Vidick alles gesammelt, was über die Quantum PCP-Vermutung bekannt ist:

Die Quanten-PCP-Vermutung

Siehe auch Thomas ' Blogbeitrag zum Thema.

Alessandro Cosentino
quelle