NP-Vollständigkeit des nicht-planaren Ising-Modells versus polynomieller Zeit-Eigenwertalgorithmen

Aus den Arbeiten von Barahona und Istrail geht hervor, dass ein kombinatorischer Ansatz verfolgt wird, um die NP-Vollständigkeit von nicht-planaren Ising-Modellen zu beweisen. Die Grundidee ist hier die Nicht-Planarität. Andererseits haben wir Polynomzeitalgorithmen zum Berechnen von Eigenwerten für Matrizen. Das verwirrt mich. Sollte das Lösen eines Ising-Modells nicht gleichbedeutend sein mit der Berechnung des Eigenwerts der Hamilton-Matrix dieses Modells? Warum ist es dann NP-vollständig? Ist das Aufstellen einer solchen Hamilton-Matrix aus erster Hand NP-vollständig? Wenn dem so ist, macht es das ganze Projekt (das Auffinden eines solchen Hamilton-Operators und dessen Lösung) NP-vollständig.

Der Algorithmus für die Matrixdiagonalisierung ist polynomial in der Größe Ihres Hilbert-Raums. Dieser Hilbert-Raum wächst jedoch exponentiell mit der Anzahl der betrachteten Gitterplätze.
@Lagerbaer, der Hilbert-Raum ist relevant, wenn wir versuchen, den Hamiltonian zu schreiben. Sollte ich also davon ausgehen, dass das Schreiben der Hamilton-Matrix, nicht das Lösen, NP-vollständig ist?
Wenn Sie den Hamilton-Operator tatsächlich vollständig ausschreiben möchten, geht dieses Problem sogar über NP-vollständig hinaus, da das Aufschreiben exponentiell viel Platz benötigt.
@Lagerbaer, jetzt bin ich noch verwirrter. Was genau ist hier NP-vollständig?
Angesichts des Hamilton-Operators für das spezielle Ising-Modell ist es NP-schwer, den Grundzustand zu finden. Der Hamilton-Operator muss nicht im Matrixformat vorliegen, was ziemlich verschwenderisch ist. Es kann in einer einfachen Form wie z H = ∑ ich , J S ich S J oder so ähnlich.
@Lagerbaer, as S ich Und S J sind Pauli-Matrizen, sollte H nicht immer in Matrixform sein? Wenn dem so ist, ist das Finden des Grundzustands für jeden Ising-Hamiltonoperator immer das Problem, die Eigenwerte zu finden, richtig? Angenommen, aus irgendwelchen Gründen, die ich nicht verstehe, liegt H nicht immer in Matrixform vor. Können wir dann sagen, dass die Grundzustände zumindest derjenigen Ising-Modelle, die Hamiltonoperatoren in Matrixform haben, in polynomieller Zeit berechnet werden können? Übrigens, was sind diese Ising-Modelle, die keinen Hamilton-Operator in Matrixform haben?

Antworten (1)

Okay, meine Kommentare werden zu viel, also werde ich antworten.

wenn ich deine frage richtig verstehe steht da folgendes:

  • Artikel zeigen, dass das nicht-planare Ising-Modell (Ermittlung seines Grundzustands) NP-vollständig ist
  • Andererseits ist das Finden der Eigenwerte einer Matrix polynomial.
  • Wie passen diese Punkte zusammen?

Der wichtige Punkt liegt hier in der Größe der Eingabe. Wenn Sie die Matrixdiagonalisierung als Unterprogramm für Ihre Lösung des Ising-Modells verwenden möchten, müssen Sie sie mit einer Matrix füttern. Die Matrix ist eine quadratische Matrix von einiger Größe M × M Wo M hängt exponentiell von der Anzahl der Gitterplätze ab. Angenommen, wir haben Ising-Spins, die entweder nach oben oder unten sein können. Dann für N Gitterplätze hat der Hilbertraum Größe M = 2 N .

Das bedeutet, dass Ihr naiver Algorithmus zur Lösung des Ising-Modells auf einem Verband mit N Seiten werden polynomial in Bezug auf sein M aber dafür exponentiell ein N .

Und was meine ich mit einem Hamiltonoperator, der nicht in Matrixform vorliegt? Nun, nehmen Sie den Ising-Hamiltonian

H = − ∑ ⟨ ich , J ⟩ J ich J σ ich σ J

Erstens, da wir über Ising-Spins sprechen, die σ sind nicht die Pauli-Matrizen! Wenn Sie die Pauli-Matrizen verwenden, haben wir es mit dem Heisenberg-Modell zu tun. Aber selbst dann wäre es nicht in "Matrixform". Mit Matrixform meine ich: Wähle eine Basis für den vollen Hilbert-Raum und schreibe dann eine Matrix für auf H in diesem Hilbertraum. Diese Matrix wird exponentiell groß sein, wie ich oben erklärt habe.

Welcher Teil dieses Arguments bricht für zusammen D ≠ 3 ? Ich hatte den Eindruck, dass das Ising-Modell nur für NP-vollständig ist D = 3 .
@Lagerbaer, ich glaube, ich weiß, was mit meinem Verständnis schief gelaufen ist. Ich bin ausgebildeter Informatiker und promoviere in Quantencomputing. Ich habe von Ising-Modellen aus Artikeln über adiabatische Quantenberechnung gelernt (nicht durch das Studium der Physik der kondensierten Materie). Abhandlungen wie diese ( www-users.math.umd.edu/~mohara/mainthesis.pdf.gz ), offensichtlich nicht falsch, aber für mich zu vereinfacht, drücken die Ising-Hamiltonoperatoren im Allgemeinen in Begriffen von Pauli-Spin-Matrizen aus. Also wurde ich mit einem begrenzten Verständnis einer Gehirnwäsche unterzogen.
@Siva, sollte es sein D ≥ 3 .
@OmarShehab, das verwirrt mich seit für D ≥ 4 , meine Feldtheorie ist "gut genug", wenn ich das richtig verstehe. Aber das liegt wahrscheinlich an der thermodynamischen Grenze, und ich denke, endliches N wäre immer noch ein Schmerz, um es genau zu lösen. :-?
Dieses Papier (DOI: 10.5488/CMP.15.43002) beschreibt ein Hybridsystem aus Ising- und Heisenberg-Spins. In Gleichung 1, σ z wird für Ising Spin und verwendet S z wird für den Heisenberg-Spin verwendet.
Nun, nur weil ein Hilbert-Raum sehr groß ist, bedeutet das nicht, dass der Grundzustand notwendigerweise schwer zu berechnen ist. Der harmonische Oszillator zum Beispiel hat einen unendlich großen Hilbert-Raum, aber der Grundzustand ist sehr einfach zu erhalten. Dies drückt die Tatsache aus, dass, obwohl wir alle wissen, dass Brute-Force-Methoden bei NP-Problemen nicht funktionieren, es möglicherweise "clevere" Algorithmen gibt, die schneller sind, wir sie nur nicht gefunden haben.
Auf die Frage, warum es z. B. bei D = 2 wäre, dass das Ising-Modell in 1 und 2 Dimensionen eine exakte Lösung hat, die wir bereits kennen: nyu.edu/classes/tuckerman/stat.mech/lectures/lecture_26/…
NP-Vollständigkeit des nicht-planaren Ising-Modells versus polynomieller Zeit-Eigenwertalgorithmen
AntwortenHierDatenschutz-Bestimmungen1y, 0v