Annäherung an quadratische, uneingeschränkte binäre Optimierungsprobleme mit Neuronalen Graph-Netzen

Annäherung an quadratische, uneingeschränkte Binäre Optimierungsprobleme mit Neuronalen Graph Netzen

Abstract:

Die derzeit verfügbare Quantum Annealing-Hardware hat aufgrund von Beschränkungen in Größe und Konnektivität noch nicht den Stand erreicht, um erfolgreich mit effizienten Algorithmen auf klassischen Computern konkurrieren zu können. Angesichts dieser Herausforderung wurde eine Herangehensweise vorgestellt, welche QUBO-Matrizen vor dem Lösen auf der Quantenhardware approximiert, indem bestimmte Einträge heraus- gestrichen werden. Dadurch reduziert sich die Größe und Komplexität des benötigten Embeddings und es werden Vorteile in Bezug auf die Größe der lösbaren Probleme sowie
die Qualität der Lösungen erwartet.
Wir werden auf diesem Ansatz aufbauen und ihn erweitern, indem wir mithilfe künstlicher neuronaler Netze versuchen, geeignete Approximationen basierend auf der Struktur der Matrix zu generieren. Das vorgeschlagene Modell besteht aus zwei separaten neuronalen Netzen: einem Graph Convolutional Network, um Eigenschaften für die Knoten im QUBO-Graphen zu berechnen und einem zweiten vollständig verbundenen Netzwerk, welches entscheidet, ob die Verbindung zwischen zwei Knoten aus der Matrix entfernt werden soll. Unter Verwendung eines genetischen Algorithmus wird das Modell trainiert, wozu Instanzen von sieben verschiedenen Problemen verwendet werden. Problemspezi-
fische Phasenübergänge wurden berücksichtigt, damit das Modell in der Trainingsphase mit einfachen als auch mit schwierigen Probleminstanzen konfrontiert wird.
Die trainierten Modelle wurden anschließend mit klassischen und quantenmechanischen Solvern evaluiert, wobei die Qualität der Lösungen der approximierten Matrix mit denen der ursprünglichen Matrix, einer anderen Approximationsstrategie und klassischen Ansätzen verglichen wurde. Die Experimente lieferten grundsätzlich zufriedenstellende Ergebnisse, teilweise konnte die approximierte Matrix bessere Ergebnisse erzielen als die ursprüngliche Matrix. Gleichzeitig wurde jedoch auch deutlich, dass dieser Ansatz nicht für alle Problemen anwendbar ist.

Autor/in:

Felix Ferdinand Mindt

Betreuer:

Studentische Abschlussarbeit | Veröffentlicht Oktober 2023 | Copyright © QAR-Lab
Anfragen zu dieser Arbeit an die Betreuer