Was genau ist Reverse Annealing?

9

Quantum Annealing (verwandte Fragen Quantum Annealing oder Hamiltonian ) ist der Prozess, der im Quantum Annealer von D-Waves verwendet wird, bei dem die Energielandschaften für verschiedene Lösungen untersucht werden und indem ein geeigneter Hamilton-Operator auf ein mögliches Optimum eingestellt wird Lösung für ein Problem. Der Prozess des Quantenglühens reduziert zusätzlich zu anderen Quanteneffekten wie Quantentunneln, Verschränkung und Überlagerung "transversale Magnetfelder" im Hamilton-Operator, die wiederum alle dazu beitragen, ein "Tal" einer quantenmechanischen Wellenfunktion auf Null zu setzen , wo die "wahrscheinlichste" Lösung liegt.

Der Prozess des umgekehrten Temperns besteht ganz kurz darin, klassische Methoden wie das simulierte Tempern zu verwenden, um eine Lösung zu finden und mithilfe des Quantenglühens in ein Tal zu gelangen. Befindet sich der vom Quantum Annealer verwendete Hamiltonianer bereits in einem "Tal", da er an erster Stelle als Lösung übergeben wird - Erreicht die D-Wave-Maschine ein anderes "Tal" (eine bessere Lösung?), Wenn der Hamiltonianer an übergeben wird? es überhaupt?

user3483902
quelle

Antworten:

4

N. Qubits aus:

                                                H.ichnichticheinl=|+0|+1...|+N.

|+ich=12(|0ich+|1ich)

Nehmen wir also an, Sie haben mit diesem Setup bereits einige Anneals ausgeführt, und eines der energiesparenden Ergebnisse scheint eine relativ gute Lösung (einige lokale Optima) für Ihr Optimierungsproblem zu sein. Bis zur jüngsten Einführung der Funktion zum umgekehrten Tempern war es unmöglich, diese Lösung als Eingabe für das nächste Tempern zu verwenden, um den lokalen Raum um diese Lösung für Bitstrings mit noch geringerer Energie zu erkunden. Reverse Annealing ermöglicht es uns daher, den Quantenglüher mit einer bekannten (klassischen) Lösung zu initialisieren und den Zustandsraum um diese lokalen Optima zu durchsuchen.

Wenn Sie komplizierte (raue) Energielandschaften mit Optimierungsproblemen erkunden, müssen Sie die globale Erkundung des Staatsraums mit der Nutzung lokaler Optima in Einklang bringen. Beim traditionellen (D-Wave) Quantenglühen beginnen wir mit einem hohen Querfeld, das dann allmählich abnimmt, wie Sie in Ihrer Frage beschrieben haben. Der Quantenglüher von D-Wave führte dabei zu Beginn des Glühplans eine globale Suche durch (aufgrund vieler Quantentunnelungen), wenn das Querfeld stark ist. Je schwächer das Querfeld wird, desto lokaler wird die Suche. Im Gegensatz dazu Reverse Annealing Beginnt mit einer vom Benutzer definierten klassischen Lösung und erhöht dann allmählich das Querfeld (Rückwärtsglühen), um dann das Querfeld wieder zu verringern (Vorwärtsglühen).

Dies führt den neuen Parameterumkehrabstand ein, der bestimmt, wie weit Sie rückwärts glühen möchten (wie stark das Querfeld werden soll). D-Wave hat die folgenden zwei Diagramme in diesem D-Wave-Whitepaper veröffentlicht :

Umkehrdistanzdiagramme

Im linken Diagramm sehen Sie, dass der Umkehrabstand ein sehr wichtiger neuer Hyperparameter ist, da sein Wert die Wahrscheinlichkeit bestimmt, einen neuen Grundzustand (blauer Bereich) zu erhalten. Wenn der Umkehrabstand zu gering ist, erhalten Sie denselben Zustand, mit dem Sie begonnen haben (roter Bereich), der unbrauchbar wäre. Und wenn Sie das Tempern zu lange rückgängig machen, führen Sie im Wesentlichen das traditionelle Quantenglühen durch und verlieren die Informationen, mit denen Sie begonnen haben. Denken Sie daran, dass zu viel Querfeld bedeutet, dass wir wieder eine globale Suche durchführen!

Das rechte Diagramm zeigt im Wesentlichen dasselbe, indem der Hamming-Abstand gegen den Umkehrabstand und die Wahrscheinlichkeit, einen neuen Grundzustand zu erhalten, aufgetragen wird. Für Ihr Problem möchten Sie diesen Sweet Spot finden (Maxima der roten Kurve). Bei großen Umkehrentfernungen sehen wir erneut, dass wir Lösungszeichenfolgen erhalten, die in Bezug auf die Hamming-Entfernung weit von unserem Ausgangszustand entfernt sind.

Alles in allem ist das umgekehrte Tempern ziemlich neu und meines Wissens gibt es keine veröffentlichten Artikel über seine Wirksamkeit. In ihrem Whitepaper behauptet D-Wave, dass "neue globale Optima bis zu 150-mal schneller erzeugt werden als das Vorwärtsquantenglühen".

Mark Fingerhuth
quelle
2

Es gibt einige Artikel über Algorithmen, die mithilfe von Reverse Annealing erstellt werden können: http://iopscience.iop.org/article/10.1088/1367-2630/aa59c4/meta und https://arxiv.org/abs/1609.05875 ( Es lohnt sich, auf frühere, etwas verwandte Arbeiten mit geschlossenen Systemen hinzuweisen: https://link.springer.com/article/10.1007/s11128-010-0168-z ). Was die experimentellen Ergebnisse angeht, denke ich, dass die einzigen, die zum Zeitpunkt des Schreibens öffentlich sichtbar waren, das Whitepaper aus dem vorherigen Beitrag sind. Auf der AQC 2018 ( https://ti.arc.nasa.gov/events/aqc-18/ ) werden jedoch Ende Juni einige neue Arbeiten vorgestellt, die in der Regel einige Monate nach der Konferenz online gestellt werden.

Nick Kanzler
quelle