Boltzmann sampling with quantum annealers via fast Stein correction

Dieser Beitrag stellt eine schnelle, approximative Stein-Korrekturmethode vor, die zufällige Merkmalsabbildungen und exponentielle Gradienten-Updates nutzt, um genaues Boltzmann-Sampling von D-Wave-Quanten-Annealern bei beliebigen Temperaturen zu ermöglichen und damit eine praktikable Alternative zu herkömmlichen Markov-Ketten-Monte-Carlo-Verfahren bietet.

Das Wesentliche

Das große Ganze: Die "verrauschte" Quantenmaschine

Stellen Sie sich eine superintelligente, hochtechnologische Maschine (einen Quantenannealer) vor, die darauf ausgelegt ist, komplexe Rätsel zu lösen. Ihre Aufgabe besteht darin, Antworten aus einer riesigen Liste von Möglichkeiten herauszufiltern. In der Welt der Physik und des maschinellen Lernens wollen wir, dass diese Maschine Antworten auf eine sehr spezifische, ausgewogene Weise auswählt, die als Boltzmann-Verteilung bezeichnet wird. Denken Sie daran als an eine "perfekt faire Lotterie", bei der jedes Los eine Gewinnchance hat, die auf einer bestimmten Regel (der Temperatur) basiert.

Es gibt jedoch ein Problem: Die Maschine ist nicht perfekt. Da es sich um ein physikalisches Gerät handelt, wird sie ein wenig "verrauscht" und macht Fehler. Anstatt die Lose fair gemäß den Regeln zu ziehen, neigt sie dazu, immer wieder dieselben wenigen Lose zu greifen oder die falschen auszuwählen. Es ist wie eine voreingenommene Lotterie-Maschine, die bestimmte Zahlen bevorzugt.

Das Problem: Wir können es nicht auf die alte Weise beheben

Normalerweise wenden Wissenschaftler bei einer voreingenommenen Maschine eine "Korrektur"-Methode an. Sie betrachten den Output der Maschine, berechnen genau, wie falsch er ist, und passen dann die Ergebnisse an.

• Der Haken: Um dies zu tun, müssen Sie das "Handbuch" der Maschine kennen (die mathematische Formel dafür, wie sie Zahlen auswählt).
• Die Realität: Bei diesen Quantenmaschinen kennt niemand das Handbuch. Es ist eine "Blackbox". Wir können die Formel dafür, wie sie Fehler macht, nicht aufschreiben, daher können wir die Standard-Korrekturwerkzeuge nicht verwenden.

Die Lösung: Eine "Blackbox"-Fixierung (Stein-Korrektur)

Die Autoren dieses Papiers verwendeten einen cleveren Trick namens Stein-Korrektur.

• Die Analogie: Stellen Sie sich vor, Sie versuchen, ein unscharfes Foto zu reparieren, aber Sie wissen nicht, wie das Originalfoto aussah. Sie wissen jedoch, wie ein "perfektes" Foto aussehen sollte (das Ziel).
• Wie es funktioniert: Anstatt zu versuchen, die inneren Zahnräder der Maschine zu reparieren, betrachtet diese Methode den Output (das unscharfe Foto) und das Ziel (das perfekte Foto). Sie weist jedem einzelnen Bild, das die Maschine produziert hat, ein "Gewicht" zu.
  • Wenn die Maschine ein Bild ausgewählt hat, das zu häufig war, gibt sie diesem Bild ein niedriges Gewicht (sie stellt es herab).
  • Wenn sie ein seltenes Bild ausgewählt hat, das häufig hätte sein sollen, gibt sie diesem Bild ein hohes Gewicht (sie hebt es hervor).
• Das Ergebnis: Indem man alle diese gewichteten Bilder zusammenzählt, erhält man ein Ergebnis, das dem "perfekten" Foto sehr nahe kommt, obwohl die Maschine selbst fehlerhaft war.

Der neue Twist: Es schnell machen (Schnelle Stein-Korrektur)

Die ursprüngliche Version dieses "Gewichtungs"-Tricks hatte eine große Geschwindigkeitsbremse.

• Der Flaschenhals: Um die Gewichte für 1.000 Bilder zu berechnen, musste der Computer eine enorme Menge an Mathematik betreiben, die lange dauerte. Wenn man 10.000 Bilder hatte, würde es ewig dauern. Es war wie der Versuch, für jedes einzelne Bild ein riesiges Sudoku-Rätsel zu lösen.
• Die Innovation: Die Autoren entwickelten eine "Schnelle" Version. Sie verwendeten zwei mathematische Abkürzungen:
  1. Random Feature Map: Anstatt jedes einzelne Detail jedes Bildes zu betrachten, erstellten sie eine vereinfachte "Skizze" der Daten. Es ist wie die Zusammenfassung eines 100-seitigen Buches zu einem einseitigen Überblick, um die Hauptidee schnell zu erfassen.
  2. Exponentiated Gradient Updates: Dies ist eine intelligente Art, die Gewichte schrittweise anzupassen, ohne die Regeln der Mathematik zu brechen.

Das Ergebnis: Ihre neue Methode ist tausende Male schneller. Sie kann riesige Mengen an Stichproben in Sekunden verarbeiten und macht sie für den Einsatz in der realen Welt praktikabel.

Was sie getestet haben

Das Team testete dies an einem echten D-Wave-Quantencomputer (einer bestimmten Art von Quantenannealer).

• Der Test: Sie baten die Maschine, spezifische physikalische Rätsel zu lösen (Ising-Modelle).
• Der Vergleich: Sie verglichen drei Dinge:
  1. Den rohen, unkorrigierten Output der Quantenmaschine.
  2. Eine traditionelle Computermethode (MCMC), die derzeit der Goldstandard ist, aber langsam sein kann.
  3. Ihre neue Schnelle Stein-Korrektur-Methode.
• Das Ergebnis: Die rohe Quantenmaschine war ziemlich ungenau. Die traditionelle Computermethode war in Ordnung. Aber die Schnelle Stein-Korrektur-Methode lieferte die genauesten Ergebnisse und schlug die traditionelle Methode in mehreren Fällen.

Das Fazit

Dieses Papier zeigt, dass wir, obwohl Quantencomputer Fehler machen und wir nicht genau wissen warum, ihre Ergebnisse mit einem neuen, superschnellen mathematischen Trick korrigieren können. Dies macht Quantencomputer für wissenschaftliche Berechnungen und maschinelles Lernen viel nützlicher und ermöglicht es ihnen potenziell, ältere, langsamere Computermethoden für bestimmte Arten von Problemen zu ersetzen.

Technische Zusammenfassung

1. Problemstellung

Die zentrale Herausforderung, die adressiert wird, ist die Unfähigkeit von Quanten-Annealern (QAs), wie denen von D-Wave hergestellt, bei beliebigen Temperaturen eine genaue Boltzmann-Stichprobenziehung durchzuführen.

• Die Lücke: Während von QAs erwartet wird, dass sie aus der Boltzmann-Verteilung $p(x) \propto e^{-\beta H(x)}$ Stichproben ziehen, weicht die tatsächliche Verteilung der von einem QA erzeugten Stichproben ($q(x)$) von der Ziel-Boltzmann-Verteilung ab.
• Einschränkung bestehender Methoden: Herkömmliche Korrekturtechniken wie Importance Sampling oder Resampling erfordern einen analytischen Ausdruck der Stichprobenverteilung $q(x) Da die Stichprobenverteilung eines QAs analytisch nicht bekannt ist, können diese Methoden nicht angewendet werden.
• Rechenengpass: Eine vorherige „Black-Box"-Methode, die Stein-Korrektur (Liu und Lee, 2017), kann Stichproben korrigieren, ohne $q(x)$ zu kennen, indem sie diese neu gewichtet. Die naive Implementierung erfordert jedoch die Lösung eines großskaligen Quadratischen Programms (QP) mit einer Zeitkomplexität von $O(n^3)$ und einer Speicherkomplexität von $O(n^2)$ (wobei $n$ die Anzahl der Stichproben ist). Dies macht sie für die in praktischen Anwendungen der Physik und des maschinellen Lernens erforderlichen großen Stichprobengrößen rechnerisch untragbar.

2. Methodik

Die Autoren schlagen einen Fast Stein Correction-Algorithmus vor, der die Stichprobengewichte effizient unter Verwendung zweier Schlüsseltechniken approximiert: Random Feature Maps und Exponentiated Gradient Descent.

A. Stein-Diskrepanz und Kernel

Die Methode nutzt die Kernelisierte Stein-Diskrepanz (KSD), um den Unterschied zwischen der Zielverteilung $p(x)$ (Boltzmann) und der Stichprobenverteilung $q(x)$ zu messen.

• Die Diskrepanz ist definiert als $S(p, q) = \mathbb{E}_{x,x' \sim q}[k_p(x, x')]$, wobei $k_p$ der Stein-Kernel ist.
• Entscheidend ist, dass der Stein-Kernel nur über die Score-Funktion $s_p(x) = \nabla \log p(x)$ von der Zielverteilung $p(x)$ abhängt. Für Boltzmann-Verteilungen ist diese Score-Funktion berechenbar, ohne die Partitionfunktion (Normierungskonstante) zu kennen.
• Das Ziel ist es, Gewichte $w_i$ für Stichproben $x_i$ zu finden, sodass die gewichtete Diskrepanz $\hat{S}(p, q) = \sum_{i,j} w_i w_j k_p(x_i, x_j)$ minimiert wird, unter der Bedingung $w_i \geq 0$ und $\sum w_i = 1$.

B. Schnelle Approximation via Random Features

Um die $O(n^3)$-Kosten der Lösung des QP zu vermeiden:

1. Random Feature Map: Der Basiskernel $k(x, x')$ wird mittels einer Random Feature Map $\phi(x)$ approximiert, sodass $k(x, x') \approx \phi(x)^\top \phi(x')$. Die Autoren verwenden eine spezifische Abbildung basierend auf der Cauchy-Verteilung für den Ising-Modell-Bereich $\{-1, 1\}^d$.
2. Linearisierung: Da der Stein-Kernel eine lineare Funktion des Basiskernels ist, kann er ebenfalls approximiert werden als $k_p(x, x') \approx \phi_p(x)^\top \phi_p(x')$, wobei $\phi_p(x)$ eine Verkettung transformierter Merkmalsvektoren ist.
3. Umformulierung: Das Optimierungsproblem wird zur Minimierung der quadrierten Norm der gewichteten Summe der Merkmalsvektoren:
   $$\min_w \left\| \sum_{i=1}^n w_i \phi_p(x_i) \right\|^2$$
   unter Simplex-Bedingungen.

C. Exponentiated Gradient Descent

Anstelle von Standard-Gradientenabstieg (der die Nicht-Negativitäts- und Normalisierungsbedingungen verletzen würde), verwenden die Autoren Exponentiated Gradient (EG)-Updates:
$$w_{t+1, i} = \frac{w_{t, i} \exp(-\eta [\nabla f(w_t)]_i)}{Z_t}$$
wobei $\eta$ die Lernrate und $Z_t$ ein Normalisierungsfaktor ist.

• Komplexitätsreduktion: Dieser Ansatz reduziert die Speicherkomplexität auf $O(n\ell)$ (wobei $\ell$ die Anzahl der Random Features ist) und die Update-Zeit auf $O(n)$, was die Verarbeitung großer Stichprobensätze ermöglicht.

3. Hauptbeiträge

1. Algorithmische Innovation: Entwicklung eines skalierbaren, approximativen Stein-Korrekturalgorithmus, der die rechnerische Komplexität in Bezug auf die Stichprobengröße $n$ von kubisch auf linear reduziert und ihn damit für den praktischen Einsatz machbar macht.
2. Verteilungskorrektur für QAs: Erfolgreiche Anwendung dieser Methode, um D-Wave-Quantenannealer-Stichproben so zu korrigieren, dass sie einer Ziel-Boltzmann-Verteilung entsprechen, ohne Kenntnis der internen Stichprobenverteilung des QAs.
3. Benchmarking: Umfassende Evaluierung an 16-Bit-Ising-Hamiltonianen (GSD-Modelle), die für D-Wave-Topologien ausgelegt sind, wobei die korrigierten Stichproben mit rohen QA-Stichproben und Standard-Markov-Ketten-Monte-Carlo (MCMC)-Methoden verglichen wurden.

4. Ergebnisse

Die Autoren testeten die Methode an den Modellen GSD 8, GSD 38 und GSD F 6 unter Verwendung eines D-Wave Advantage System 6.2.

• Effizienz: Die Fast Stein Correction war um Größenordnungen schneller als die exakte QP-basierte Korrektur. Mit $\ell=5.000$ Random Features war der Restfehler der Kernel-Matrix-Approximation ausreichend gering.
• Genauigkeitsverbesserung:
  • Thermische Mittelwerte: Die Methode reduzierte den Restfehler für die Berechnung der Inneren Energie ($E$), der Magnetischen Suszeptibilität ($\chi$) und des Binder-Cumulant ($U_4$) über einen Bereich inverser Temperaturen ($\beta$) erheblich.
  • Vergleich: In allen getesteten Fällen übertraf die Genauigkeit der Fast Stein Correction (SC) die rohen Quantenannealer (QA)-Stichproben.
  • vs. MCMC: Bemerkenswerterweise war der Fehler der Fast Stein Correction konsistent kleiner als der der Standard-Metropolis-MCMC-Methode.
• Stichprobengröße: Die Methode behielt bei $n=10.000$ Stichproben eine hohe Genauigkeit bei und demonstrierte damit ihre Skalierbarkeit.

5. Bedeutung und Fazit

• Lebensfähigkeit von QAs: Die Ergebnisse deuten darauf hin, dass Quantenannealer, in Kombination mit der Fast Stein Correction, als eine viable und potenziell überlegene Alternative zu etablierten MCMC-Methoden für die Boltzmann-Stichprobenziehung hervortreten können.
• Globale Mischung: Die Autoren heben hervor, dass MCMC oft unter langsamer Mischung leidet (Steckenbleiben in lokalen Minima), während QA-Stichproben weniger lokal konzentriert sind. Die Stein-Korrektur gewichtet diese diversen Stichproben effektiv neu, um der Zielverteilung zu entsprechen, und nutzt dabei die Fähigkeit des QAs, den globalen Raum zu erkunden.
• Breitere Auswirkungen: Dieser Ansatz ist nicht auf QAs beschränkt; er ist auf andere verrauschte Quantengeräte (NISQ) und Ising-Maschinen (z. B. Coherent Ising Machines, GPU-basierte Löser) anwendbar, bei denen die Stichprobenverteilung unbekannt oder verrauscht ist.
• Zukünftige Arbeiten: Die Autoren planen, diese Methode auf Aufgaben des maschinellen Lernens und Probleme der statistischen Physik anzuwenden, die stark eingeschränkte Räume betreffen, in denen eine globale Mischung schwierig ist.

Zusammenfassend schließt das Papier eine kritische Lücke zwischen theoretischen Fähigkeiten des Quanten-Annealing und praktischer statistischer Stichprobenziehung, indem es ein rechnerisch effizientes „Black-Box"-Korrekturtool bereitstellt, das die Genauigkeit von quantengenerierten Stichproben erheblich verbessert.