Enhancing QAOA using QRAC encoding for combinatorial optimization problems

Klassische Ansätze des Hochleistungsrechnens für klassische Optimierungsprobleme stoßen mit zunehmender Problemgröße auf Skalierbarkeitsprobleme. Der Quantum Approximate Optimization Algorithm (QAOA) bietet einen vielversprechenden Ansatz zur Überwindung der Einschränkungen klassischer Algorithmen. Allerdings schränkt die Anzahl fehlertoleranter Qubits seine Anwendbarkeit auf aktueller Quantenhardware stark ein. Um dies zu mildern, untersuchen wir die Verwendung von QRAC, das mehrere Bits in einem einzigen Qubit codieren kann. Diese Arbeit untersucht das Potenzial von QRAC-basierten Kodierungsschemata für kombinatorische Optimierungsprobleme. Die zentrale Forschungsfrage lautet: Wie wirkt sich die QRAC-basierte Kodierung auf die Leistung von QAOA bei der Lösung kombinatorischer Optimierungsprobleme aus?Wir haben ein neuartiges QAOA-Framework entwickelt, das die Verwendung von QRAC-kodierten Hamilton-Operatoren ermöglicht, sowie das entsprechende Dekodierungs-Framework, das die Quantenresultate zurück in einen klassischen Lösungsraum abbildet. Wir haben systematische Experimente durchgeführt, bei denen wir unseren Workflow auf mehrere TSP- und BPP-Instanzen angewendet haben, die weit verbreitete, repräsentative kombinatorische Optimierungsprobleme sind. Diese Instanzen variieren in Größe, Gewicht, Lösungen und Einschränkungen. Wir haben verschiedene Einstellungen unseres Workflows verglichen und unsere Ergebnisse zu Laufzeit, Lösungsgenauigkeit, Skalierbarkeit und Qubit-Kompressionsrate dokumentiert.Unsere Ergebnisse zeigen ein aufschlussreiches, aber gemischtes Bild. Bei kleineren Problemfällen mit strengeren Beschränkungsstrukturen (d. h. weniger Städten für ein TSP und weniger Behältern für ein BPP) lieferte QRAC+QAOA in 60 bis 80 % der Durchläufe interpretierbare Lösungen. Der Ansatz lässt sich jedoch nicht zuverlässig auf komplexere Fälle skalieren, z. B. das 5-Städte-TSP und das uneingeschränkte BPP, bei denen es nur wenige realisierbare Lösungen gibt. Der Hauptvorteil der QRAC-Kodierung besteht in ihrer Fähigkeit, Probleme zu simulieren, die aufgrund von Qubit-Beschränkungen auf unserer Hardware sonst nicht möglich wären. Entscheidend ist, dass wir festgestellt haben, dass die Effizienz der QRAC-Komprimierung stark vom jeweiligen Problem abhängt, wobei spärliche Interaktionsgraphen eine bessere Zuordnung ermöglichen als dichte. Diese Arbeit liefert eine der ersten empirischen Untersuchungen zum Verhalten von QRAC+QAOA bei der Lösung kombinatorischer Probleme und quantifiziert die Kompromisse zwischen Komprimierungsrate und Lösungsqualität. Wir kommen zu dem Schluss, dass QRAC zwar eine vielversprechende Richtung für die Erweiterung der Reichweite der Quantenoptimierung in der NISQ-Ära ist, in seiner derzeitigen Form jedoch am besten für mittelgroße Probleme mit inhärenten strukturellen Einschränkungen geeignet ist. Diese Arbeit legt den Grundstein für zukünftige Forschung zu robusteren Kodierungsstrategien und hybriden quantenklassischen Algorithmen.