Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)

Dieser Artikel zeigt, dass die Parallelisierung des Hamiltonian Auto Decomposition Optimisation Framework (HADOF) auf einzelnen und mehreren IBM-Quantenprozessoren die Wandzeit zur Lösung großskaliger kombinatorischer Optimierungsprobleme, einschließlich realer Genome-Assembly-Instanzen, erheblich reduziert, während die Lösungsqualität beibehalten wird und Fortschritte hin zum Hochleistungs-Quantencomputing erzielt werden.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, ein riesiges, unglaublich komplexes Puzzle zu lösen. Dies ist kein gewöhnliches Puzzle; es ist ein „Quantenpuzzle", das ein reales Problem darstellt, wie etwa das Herausfinden der korrekten Reihenfolge von DNA-Strängen, um ein Genom zusammenzusetzen.

Das Problem besteht darin, dass das Puzzle für eine einzelne Person (oder einen einzelnen Quantencomputer) zu groß ist, um es in den Händen zu halten. Die Teile sind zu zahlreich, und das „Rauschen" im Raum (Hardwarefehler) erschwert es, das Bild klar zu erkennen. Wenn Sie versuchen, das gesamte Puzzle auf einen kleinen Tisch zu zwingen, passt es nicht, und Sie werden wahrscheinlich Fehler machen.

Dieser Artikel stellt eine neue Strategie vor, die HADOF (Hamiltonian Auto Decomposition Optimisation Framework) genannt wird, um dies zu lösen. So funktioniert es, unter Verwendung einfacher Analogien:

1. Das Problem: Das „zu-groß-um-es-zu-halten"-Puzzle

Aktuelle Quantencomputer sind wie winzige, verrauschte Werkbänke. Sie können nur wenige Puzzlestücke gleichzeitig halten. Wenn Sie versuchen, ein riesiges Problem (wie ein Genom mit Tausenden von DNA-Fragmenten) auf einmal auf einer dieser Werkbänke zu lösen, wird der Computer überfordert, die Teile werden durch „Rauschen" durcheinandergebracht, und die Lösung scheitert.

2. Die Lösung: Aufteilen in „Mini-Puzzles"

Anstatt zu versuchen, das riesige Puzzle auf einen Schlag zu lösen, agiert HADOF wie ein Meisterorganisator. Es zerlegt das massive Puzzle in hunderte winziger, handhabbarer „Mini-Puzzles" (Teilprobleme).

• Der Zaubertrick: Es zerschneidet das Puzzle nicht einfach zufällig. Es nutzt ein intelligentes System, um die bereits platzierten Teile zu betrachten und diese Information zu nutzen, um das nächste Mini-Puzzle zu lösen.
• Die Iteration: Es löst ein Mini-Puzzle, lernt daraus, aktualisiert sein Verständnis des Gesamtbildes und löst dann das nächste. Es wiederholt dies, bis das gesamte Bild klar ist.

3. Die neue Wendung: Das „Fließband" (Parallelisierung)

Früher funktionierte diese Methode wie ein einzelner Arbeiter auf einem Fließband: Mini-Puzzle #1 lösen, dann #2, dann #3. Das dauert lange.

Die Autoren dieses Artikels haben das System so verbessert, dass es wie eine lebendige Fabrik mit mehreren Fließbändern läuft.

• Einzelner Arbeiter vs. Team: Anstatt dass eine Person die Mini-Puzzles nacheinander löst, nutzten sie ein Team von Arbeitern (mehrere Quantencomputer oder QPUs), um verschiedene Mini-Puzzles zur exakt gleichen Zeit zu lösen.
• Das Ergebnis: Sie stellten fest, dass sie durch den Einsatz eines Teams von vier Quantencomputern die Aufgabe 3- bis 4-mal schneller abschließen konnten als mit nur einem. Selbst bei Verwendung nur eines Computers, aber mit einer parallelen Organisation der Arbeit, war es 3-mal schneller.

4. Der Realwelt-Test: Wiederherstellung einer DNA-„Geschichte"

Um zu beweisen, dass dies in der realen Welt funktioniert, testete das Team dies an einem spezifischen biologischen Problem: Genom-Assembly.

• Die Analogie: Stellen Sie sich vor, Sie haben ein Buch in Tausende winziger Papierstreifen (DNA-Reads) zerrissen. Ihre Aufgabe ist es, sie in der richtigen Reihenfolge wieder zusammenzukleben, um die Geschichte lesen zu können.
• Der Test: Sie nahmen einen echten biologischen Datensatz (ein Virus namens $\phi$X174) und versuchten, es mit ihrem neuen „Team von Quantencomputern" wiederherzustellen.
• Das Ergebnis:
  • Geschwindigkeit: Der parallele Ansatz war viel schneller darin, ein Ergebnis zu erzielen.
  • Qualität: Obwohl die verrauschten Quantencomputer keine perfekten 100%-Punkte erzielten (aufgrund des Hardware-Rauschens), fanden sie dennoch sehr gute Lösungen. Tatsächlich waren über 50 % der von ihnen generierten Lösungen gut genug, um mit Standard-Nachverarbeitungswerkzeugen zur perfekten Antwort korrigiert zu werden.
  • Vergleich: Als sie versuchten, das gesamte DNA-Puzzle auf einem einzelnen Quantencomputer ohne Aufteilung zu lösen, scheiterte der Computer daran, eine gute Lösung zu finden. Die „Auf-teile-methode" (HADOF) hatte Erfolg, wo die „Alles-auf-einen-Streich"-Methode scheiterte.

5. Das große Ganze: „High Performance Quantum" (HPQ)

Die Autoren bezeichnen diesen Ansatz als High Performance Quantum (HPQ) Computing.

• Denken Sie an den Unterschied zwischen einer einzelnen Person, die versucht, einen Sandberg mit einem Löffel zu bewegen, und einem Fuhrpark von Lastwagen, die zusammenarbeiten.
• Der Artikel argumentiert, dass wir, um Quantencomputer für große Probleme wirklich nützlich zu machen, nicht einfach darauf warten können, dass sie größer und leiser werden. Wir müssen ändern, wie wir sie nutzen: indem wir Probleme in kleine Teile zerlegen und sie parallel über viele Maschinen hinweg lösen.

Zusammenfassung der Behauptungen

• Geschwindigkeit: Die parallele Verwendung mehrerer Quantencomputer macht die Lösung dieser Probleme 3–4-mal schneller.
• Skalierbarkeit: Diese Methode ermöglicht es uns, Probleme (wie 500 Variablen) zu lösen, die derzeit für einen einzelnen Quantencomputer zu groß sind, um sie zu bewältigen.
• Genauigkeit: Selbst mit verrauschter, unvollkommener Hardware findet diese Methode bessere Lösungen als der Versuch, das gesamte Problem auf einmal zu lösen.
• Reale Anwendung: Sie hat dies erfolgreich an einer realen Genom-Assembly-Aufgabe demonstriert und gezeigt, dass es nicht nur eine Theorie, sondern ein funktionierendes Werkzeug ist.

Kurz gesagt sagt der Artikel: „Versuchen Sie nicht, den ganzen Elefanten auf einen Bissen zu essen. Zerlegen Sie ihn in kleine Stücke und lassen Sie ein Team von Quantencomputern sie alle gleichzeitig essen. Es ist schneller und es funktioniert besser."

Technische Zusammenfassung

1. Problemstellung

Die praktische Anwendung der Quantenoptimierung für kombinatorische Probleme (formuliert als Quadratic Unconstrained Binary Optimization, oder QUBO) wird derzeit durch die Grenzen von Noisy Intermediate-Scale Quantum (NISQ)-Geräten behindert. Zu den wichtigsten Einschränkungen gehören:

• Begrenzte Qubit-Anzahlen: Die aktuelle Hardware kann keine großen QUBO-Probleme mit Hunderten von Variablen hosten.
• Hardware-Rauschen: Die Anhäufung von Rauschen in tiefen Schaltungen verschlechtert die Lösungsqualität.
• Skalierbarkeit: Bestehende Zerlegungsmethoden (wie HADOF) sind überwiegend sequenziell und nutzen die Parallelität in verteilten Quantenarchitekturen oder High-Performance-Computing (HPC)-Ressourcen nicht aus.
• Simulationsgrenzen: Die klassische Simulation großer Quantenschaltungen ist rechenintensiv und speicherhungrig.

Das Papier adressiert diese Probleme, indem es das Hamiltonian Auto Decomposition Optimisation Framework (HADOF) um die Unterstützung einer parallelen Ausführung über einzelne und mehrere Quantum Processing Units (QPUs) erweitert, um High Performance Quantum (HPQ) Computing zu erreichen.

2. Methodik

Kernframework: HADOF

HADOF zerlegt einen globalen QUBO-Hamiltonoperator in kleinere, handhabbare Teil-Hamiltonoperatoren, die iterativ gelöst werden können.

1. Zerlegung: Das globale Problem wird in Teilprobleme (Teilmengen von Variablen) aufgeteilt.
2. Iterative Lösung: Jedes Teilproblem wird mit einem Quantenoptimierer (QAOA) gelöst.
3. Kontextintegration: Die Erwartungswerte ($E[x_i]$) der Variablen aus gelösten Teilproblemen werden verwendet, um den Kontext für nachfolgende Teilprobleme zu approximieren.
4. Aggregation: Die Lösungen werden wieder kombiniert, um eine globale Lösung zu bilden.

Die parallele Erweiterung

Die Autoren führen eine parallelisierte Version von HADOF ein, die sich in zwei wesentlichen Punkten von der sequenziellen Basislinie unterscheidet:

• Unabhängige Generierung: In jeder Iteration werden alle Teil-Hamiltonoperatoren gleichzeitig unter Verwendung der Erwartungswerte aus der vorherigen Iteration generiert (anstatt Werte innerhalb der aktuellen Iteration sequenziell zu aktualisieren).
• Asynchrone Ausführung: Teilschaltungen werden parallel gelöst. Dies ermöglicht:
  • Intra-QPU-Parallelität: Ausführung mehrerer Jobs auf einer einzelnen QPU (Nutzung des Schedulers).
  • Inter-QPU-Parallelität: Verteilung von Jobs auf mehrere verschiedene QPUs (z. B. IBM Kingston, Pittsburgh, Fez, Marrakesh).

Implementierungsdetails

• Optimierer: Verwendung eines digitalisierten QAOA-Ansatzes mit Trotterisierter Annealing-Parametrisierung, um klassische Optimierungsschleifen für die Parameter $\beta$ und $\gamma$ zu vermeiden.
• Schaltungstiefe: Schaltungen werden schichtweise aufgebaut (bis zu 5 Schichten). In jeder Iteration wird eine Schicht zu allen Teilschaltungen hinzugefügt.
• Teilproblemgröße: Festgelegt auf 5 Qubits ($k=5$), um auf aktueller Hardware eine hohe Fidelität zu gewährleisten.
• Zielanwendung: Genomassemblierung, modelliert als Travelling Salesman Problem (TSP) auf einem Überlappungsgraphen. Das Problem wird in ein QUBO kodiert, wobei das Ziel darin besteht, den Hamiltonschen Pfad zu finden.

3. Hauptbeiträge

1. Erste HADOF-Implementierung auf Realgeräten: Die Studie überführt HADOF von der theoretischen Simulation zur Ausführung auf echten IBM QPUs (Kingston, Pittsburgh, Fez, Marrakesh).
2. Parallelisierungsstrategie: Demonstration eines Frameworks für die gleichzeitige Ausführung zerlegter Teilprobleme, das signifikante Beschleunigungen der Wandzeit bei unveränderter Lösungsqualität erzielt.
3. Validierung des HPQ-Paradigmas: Positionierung von HADOF als gangbarer Weg hin zum High Performance Quantum Computing durch die Integration algorithmischer Zerlegung mit systemweiter Parallelität.
4. Anwendung in der realen Welt: Erfolgreiche Anwendung des Frameworks auf ein Genomassemblierungsproblem (Bakteriophage ϕX174), was seinen Nutzen in der computergestützten Biologie demonstriert.
5. Benchmarking: Umfassender Vergleich zwischen sequenziellem HADOF, parallelem HADOF (Single- und Multi-QPU), Standard-Vollschnitt-QAOA und klassischer Simulierter Abkühlung (Simulated Annealing).

4. Wichtige Ergebnisse

Geschwindigkeit und Effizienz

• Wandzeit:
  • Multi-QPU-Parallel: Erzielte eine 3–4-fache Reduzierung der Wandzeit im Vergleich zur sequenziellen Ausführung auf echter Hardware.
  • Single-QPU-Parallel: Erzielte selbst auf einem einzelnen Gerät eine bis zu 3-fache Beschleunigung durch effiziente Job-Orchestrierung.
  • Simulation: Vorhergesagte >5-fache Beschleunigung in parallelen Simulationsmodi.
• QPU-Nutzung: Während die gesamte QPU-Nutzungszeit proportional zur Anzahl der Schaltungen bleibt, wird die Makespan (Gesamtzeit bis zur Lösung) drastisch reduziert, was den Ansatz für zeitkritische Anwendungen praktikabel macht.

Genauigkeit und Robustheit

• vs. Standard-QAOA: HADOF schneidet auf echter Hardware deutlich besser ab als der Vollschicht-QAOA.
  • Die Genauigkeit von Standard-QAOA fiel bei 50-Variablen-Problemen auf rauer Hardware aufgrund von Rauschanhäufung auf nahezu Null (z. B. 0,02).
  • HADOF hielt auf echter Hardware für ähnliche Größen eine Genauigkeit von >0,80 aufrecht.
• Rauschresistenz: Die Zerlegung begrenzt die Schaltungstiefe und verhindert die exponentielle Verschlechterung der Genauigkeit, die bei monolithischen Schaltungen zu beobachten ist.
• Fallstudie Genomassemblierung:
  • Ideale Simulation: Sowohl sequenzielles als auch paralleles HADOF erreichten 100 % beste Genauigkeit (entsprechend Simulierter Abkühlung).
  • Echte Hardware: Die beste Genauigkeit blieb wettbewerbsfähig (0,88–0,91), obwohl die Häufigkeit, den exakten Grundzustand zu finden, aufgrund von Rauschen auf Null sank. Dennoch konnten >52 % der gesampelten Lösungen nachbearbeitet werden, um die korrekte Sequenz mit Standard-Bioinformatik-Tools (GFAtools) wiederherzustellen.

Skalierbarkeit

• HADOF löste erfolgreich QUBO-Probleme mit bis zu 500 Variablen in der Simulation und 300 Variablen auf echter Hardware unter Verwendung von nur 5-Qubit-Schaltungen.
• Standard-Vollschicht-QAOA ist auf derselben Hardware aufgrund von Konnektivitäts- und Einbettungsbeschränkungen auf ca. 50 Variablen begrenzt.

5. Bedeutung und Fazit

Diese Forschung zeigt, dass Zerlegung und Parallelität nicht nur Workarounds für aktuelle Hardwarebeschränkungen sind, sondern fundamentale Enabler für einen praktischen Quantenvorteil.

• Skalierbarkeit: HADOF umgeht die physikalischen Qubit-Grenzen aktueller Geräte und ermöglicht die Lösung von Problemen, die weit größer sind als die nativ von der Hardware unterstützten.
• HPQ-Ausrichtung: Das Framework stimmt mit dem aufkommenden High Performance Quantum Computing-Paradigma überein und zeigt, dass verteilte Quantenarchitekturen erhebliche Leistungsgewinne liefern können.
• Praktische Durchführbarkeit: Durch die erfolgreiche Anwendung der Methode auf die Genomassemblierung beweist das Papier, dass Quantenoptimierung in reale wissenschaftliche Pipelines integriert werden kann, sofern das Rauschen durch Zerlegungs- und Parallelisierungsstrategien gemanagt wird.

Die Autoren kommen zu dem Schluss, dass zukünftige Arbeiten sich auf adaptive Zerlegungsstrategien, Fehlerminderungstechniken und die Integration von HADOF in Standard-Genomassemblierungspipelines mit echten Sequenzierungsdaten konzentrieren sollten.