Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer

In dieser Arbeit demonstrieren die Autoren die experimentelle Realisierung eines Quanten-Markov-Ketten-Monte-Carlo-Algorithmus (qMCMC) auf den Quantencomputern H2 und Helios von Quantinuum und zeigen, dass trotz des Rauschens aktueller NISQ-Hardware präzise Ergebnisse erzielt werden können.

Das Wesentliche

Hier ist eine einfache Erklärung der wissenschaftlichen Arbeit, verpackt in eine Geschichte für den Alltag.

Die große Reise: Wie Quantencomputer den "zufälligen Spaziergang" meistern

Stellen Sie sich vor, Sie wollen herausfinden, wie viel Geld im Durchschnitt in einer riesigen Stadt in den Taschen der Menschen steckt.

Der klassische Weg (wie wir es heute machen):
Sie schicken einen Boten los. Dieser Bot geht zufällig von Haus zu Haus (das nennt man einen Markov-Zufallspaziergang). Er klopft an, schaut kurz in die Tasche, notiert den Betrag und geht zum nächsten zufälligen Haus. Er muss dies Tausende von Malen wiederholen, bis er ein gutes Gefühl für den Durchschnitt hat. Das dauert lange und ist oft ungenau, weil der Bot manchmal im selben Viertel herumirrt.

Der Quanten-Weg (was diese Forscher getestet haben):
Die Forscher von Qubit Pharmaceuticals und der National University of Singapore haben einen neuen Trick ausprobiert. Sie haben diesen "Boten" in einen Quantencomputer verwandelt.

Statt nur einen Boten zu schicken, der einen Weg geht, nutzt der Quantencomputer das Prinzip der "Überlagerung". Stellen Sie sich vor, Ihr Quanten-Boten ist wie ein Geist, der gleichzeitig auf allen Straßen der Stadt läuft. Er sammelt Informationen von Millionen von Häusern gleichzeitig.

Was haben die Forscher genau gemacht?

Die Forscher haben auf echten Quantencomputern (den Maschinen "H2" und "Helios" von Quantinuum) getestet, ob man diesen "Geist-Boten" tatsächlich steuern kann, um die richtige Antwort zu finden.

Sie haben verschiedene Methoden ausprobiert, um diesen Quanten-Boten zu programmieren:

1. Die "Lineare Kombination" (Das Misch-Verfahren):
   Stellen Sie sich vor, Sie haben zwei verschiedene Karten für den Weg. Eine sagt "Geh geradeaus", die andere "Dreh links". Der Quanten-Boten hält beide Karten gleichzeitig in der Hand und geht einen Weg, der eine perfekte Mischung aus beiden ist. Das erlaubt ihm, viel schneller das Ziel zu erreichen.

2. Die "Szegedy-Methode" (Der Spiegel-Trick):
   Hier nutzen die Forscher einen cleveren mathematischen Trick. Sie bauen einen Spiegel, der den Weg des Boten so reflektiert, dass er genau dort landet, wo er sein soll (die "stationäre Verteilung"). Es ist, als würde man einen Ball in einem Labyrinth so werfen, dass er durch die Wände hindurchgeht und direkt am Ausgang landet, statt gegen jede Wand zu prallen.

3. Der "Dual Space" (Die Rückseite der Medaille):
   Manchmal ist es einfacher, nicht den Weg des Boten zu verfolgen, sondern die Wahrscheinlichkeit, dass er einen Weg nimmt. Die Forscher haben einen Weg gefunden, der die komplizierten "Ja/Nein"-Entscheidungen (wird der Schritt akzeptiert oder abgelehnt?) im Hintergrund erledigt, ohne den Boten aufzuhalten.

Das Ergebnis: Ein Erfolg trotz "Rauschen"

Quantencomputer sind heute noch wie neugeborene Kinder: Sie sind unglaublich klug, aber sie sind auch sehr empfindlich. Ein kleines Rauschen (wie ein lautes Geräusch im Raum) kann sie verwirren. Das nennt man "Noisy Intermediate Scale Quantum" (NISQ).

Die große Überraschung dieser Studie ist: Es hat funktioniert!

• Die Forscher haben gezeigt, dass man auf diesen "empfindlichen" Maschinen bereits jetzt sehr genaue Ergebnisse erzielen kann.
• Sie haben den "Geist-Boten" erfolgreich durch das Labyrinth geschickt und den Durchschnittswert berechnet.
• Die Ergebnisse stimmten zu etwa 90 % mit der theoretischen Vorhersage überein.

Warum ist das wichtig?

Stellen Sie sich vor, Sie sind ein Chemiker, der ein neues Medikament entwickelt. Sie müssen berechnen, wie sich Millionen von Molekülen verhalten.

• Heute: Ein klassischer Computer braucht dafür Wochen oder Monate, weil er die Moleküle nacheinander durchrechnet.
• Mit dieser Methode: Ein Quantencomputer könnte diese Berechnung in einem Bruchteil der Zeit erledigen, weil er alle Möglichkeiten gleichzeitig "spürt".

Das Fazit in einem Satz

Die Forscher haben bewiesen, dass wir die "Zufallspaziergänge" der Zukunft nicht mehr langsam auf dem Boden laufen lassen müssen, sondern sie als fliegende Quanten-Geister durch die Welt schicken können – und das funktioniert bereits jetzt auf den heutigen, noch fehleranfälligen Maschinen. Es ist ein entscheidender Beweis dafür, dass die Zukunft der Simulationen (für Chemie, Physik und KI) bereits begonnen hat.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer" auf Deutsch:

Titel: Experimentelle Realisierung des Markov-Chain-Monte-Carlo-Algorithmus auf einem Quantencomputer

Autoren: Baptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal
Institutionen: Qubit Pharmaceuticals, Sorbonne Université, Centre for Quantum Technologies (Singapur)
Hardware: Quantinuum H2-1, H2-2 und Helios (Ionenfallen-Quantencomputer)

---

1. Problemstellung

Quantenalgorithmen versprechen für bestimmte Sampling-Aufgaben eine quadratisch verbesserte Komplexität im Vergleich zu klassischen Methoden. Ein prominentes Beispiel ist der Quantum Amplitude Estimation (QAE)-Algorithmus, der die Schätzung des Erwartungswerts von Funktionen beschleunigen kann, sofern der Quantenzustand der zu sampelnden Wahrscheinlichkeitsverteilung zugänglich ist.

Klassisch werden solche Verteilungen oft durch das Ausführen von Schritten einer Markov-Kette (bis zur Konvergenz gegen die stationäre Verteilung) generiert. Die Herausforderung besteht darin, diese klassischen Markov-Ketten effizient in unitäre Quantenoperationen zu übersetzen, um sie auf aktuellen, fehleranfälligen Quantenhardwaren (NISQ-Ära) auszuführen. Während große Fehlerkorrektur noch fern ist, müssen Algorithmen und Hardware-Implementierungen so optimiert werden, dass sie mit den begrenzten Ressourcen und Rauschen heutiger Geräte zurechtkommen.

2. Methodik

Das Team führte experimentelle Tests verschiedener Kodierungstechniken für Markov-Kern-Operatoren auf Quantencomputern durch. Der Fokus lag auf einer zweizuständigen Markov-Kette ($S = \{0, 1\}$) mit einem symmetrischen Kern $P$.

Die Studie verglich vier verschiedene Ansätze zur Kodierung und Vorbereitung der stationären Verteilung $\pi$:

1. Lineare Kombination von Unitären (LCU):

   • Der Markov-Kern $P$ wird als gewichtete Summe von Unitären dargestellt ($P = (1-\delta)I + \delta X$).
   • Eine unitäre Operation $U$ wird auf einen Ancilla-Qubit und den Zustandsraum angewendet.
   • Der resultierende „qubitized walk operator" $W$ wird genutzt, um den stationären Zustand $|\pi\rangle$ mittels Phasenschätzung vorzubereiten.

2. Szegedy-Quantisierung:

   • Basierend auf Szegedys Methode wird ein unitärer Operator $O$ konstruiert, der die Übergangswahrscheinlichkeiten kodiert.
   • Der Walk-Operator wird als $W = O Z O^\dagger S$ definiert (unter Verwendung des SWAP-Operators $S$).
   • Dies kodiert die Spektraleigenschaften der Diskriminantenmatrix der Markov-Kette.

3. Controlled-SWAP Kodierung (Metropolis-Hastings):

   • Die Markov-Kette wird als Metropolis-Hastings-Prozess interpretiert.
   • Ein Vorschlagskern ($T=X$) und eine Akzeptanzwahrscheinlichkeit ($\delta$) werden verwendet.
   • Die Kodierung erfolgt über einen kontrollierten SWAP-Operator und Akzeptanz-Unitären.

4. Dualer Raum (Dual Space) für Metropolis-Hastings:

   • Ein neuartiger Ansatz, der den Quantenschritt-Operator auf Paaren von Zuständen (Dual Space) kodiert.
   • Dies vermeidet den Overhead, Akzeptanz-/Ablehnungswahrscheinlichkeiten explizit zu verfolgen.
   • Ein zentrales Ziel war hier, zu verifizieren, dass der vorbereitete Zustand ein Eigenvektor des Walk-Operators ist.

Experimenteller Ablauf:

• Zustandspräparation: Vorbereitung des stationären Zustands $|\pi\rangle$ unter Verwendung der oben genannten Methoden.
• Amplitude Estimation: Schätzung des Erwartungswerts einer Funktion $f(x)$ (hier $f(x) = \delta_1(x)$) unter Verwendung von QAE.
• Validierung: Messung der Überlappung (Overlap) zwischen dem vorbereiteten Zustand und dem Eigenzustand des Walk-Operators, um die Korrektheit der Implementierung zu bestätigen.

3. Wichtige Beiträge und Ergebnisse

• Erfolgreiche NISQ-Implementierung: Die Autoren demonstrierten, dass präzise Ergebnisse auf aktuellen Quantencomputern (H2-1, H2-2, Helios) erzielt werden können, obwohl diese noch keine vollständige Fehlerkorrektur besitzen.
• Vergleich der Kodierungen:
  • Die LCU-Methode lieferte in 90 % der Experimente den korrekten Erwartungswert. Der verwendete Schaltkreis umfasste 237 Gatter auf 6 Qubits.
  • Die Szegedy-Methode zeigte eine Erfolgswahrscheinlichkeit von 0,5 bei der Zustandspräparation, was exakt der theoretischen Vorhersage (basierend auf dem Überlapp von Start- und stationärer Verteilung) entspricht.
  • Bei der Controlled-SWAP-Methode wurde der erwartete Phasenwert mit einer Erfolgsrate von 93 % gemessen.
  • Der duale Metropolis-Hastings-Ansatz zeigte eine Überlappung von ca. 2/3 zwischen dem Eigenvektor vor und nach Anwendung des Walk-Operators (Helios lieferte hier die besten Ergebnisse).
• Grenzen der aktuellen Hardware: Die Ergebnisse deuten darauf hin, dass Schaltkreise mit einer Tiefe von etwa 250 elementaren Gattern (bzw. bis zu 500 Gattern in komplexeren Fällen) die aktuelle Grenze für quantitativ aussagekräftige Monte-Carlo-Schätzungen auf diesen NISQ-Geräten darstellen.
• Datenqualität: Die gemessenen Wahrscheinlichkeitsverteilungen stimmten in allen Fällen sehr gut mit den theoretischen Erwartungen überein (z. B. bei der stationären Verteilung $\pi = (0.5, 0.5)$).

4. Bedeutung und Ausblick

Dieses Paper liefert einen entscheidenden Proof of Concept für die Skalierung von Quanten-Hardware-Simulationen. Es zeigt, dass die quadratische Beschleunigung von Markov-Chain-Monte-Carlo (MCMC) Algorithmen auch auf physikalischen Qubits nutzbar ist, wenn die Algorithmen sorgfältig an die Hardware angepasst werden.

• Anwendungsgebiete: Die Methode hat breite Anwendungen in der statistischen Physik, computergestützten Chemie, bayesschen Inferenz und maschinellem Lernen.
• Zukünftige Schritte:
  • Durchführung ähnlicher Experimente auf zukünftigen Geräten mit verbesserter Gate-Qualität.
  • Erweiterung auf nicht-reversible Markov-Ketten.
  • Implementierung von fehlerkorrigierten Versionen dieser Schaltkreise, um niedrigere Fehlerraten auf logischen Qubits zu erreichen.

Zusammenfassend beweist die Arbeit, dass durch die Kombination aus tiefem Verständnis der Quantengeräte, Middleware-Stacks und algorithmischer Optimierung (insbesondere effiziente Kodierungen) bereits heute sinnvolle quantenmechanische Simulationen durchgeführt werden können, die über reine Proof-of-Concepts hinausgehen.