Enhancing QAOA using QRAC encoding for combinatorial optimization problems

Abstract

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.

Classical high-performance computing (HPC) approaches to classical optimization problems face scalability issues as problem sizes grow. The Quantum Approximate Optimization Algorithm (QAOA), offers a promising approach for overcoming the limitations and constraints of classical algorithms; however, the number of fault-tolerant qubits strongly limits its applicability on current quantum hardware. To mitigate this, we explore the use of QRAC, which can encode up to multiple bits in a single qubit. This thesis investigates the potential of QRAC-based encoding schemes for combinatorial optimization problems. The central research question asks: How does QRAC-based encoding impact the performance of QAOA in solving combinatorial optimization problems?We have developed a novel QAOA framework, which enables the use of QRAC-encoded Hamiltonians, along with the corresponding decoding framework, that maps the quantum results back into a classical solution space. We conducted systematic experiments, where we applied our workflow on several TSP and BPP instances, which are widely studied, representative combinatorial optimization problems. These instances vary in size, weights, solutions, and constraints. We compared different settings of our workflow and reported our findings on runtime, solution accuracy, scalability, and qubit compression rate.Our results reveal an insightful but mixed picture. For smaller problem instances with tighter constraint structures (i.e., fewer cities for a TSP and fewer bins for a BPP), QRAC+QAOA produced interpretable solutions in 60-80% of runs. However, the approach does not scale reliably to more complex instances, such as the 5-city TSP and the unrestricted BPP, where feasible solutions are scarce. Notably, the primary advantage of QRAC encoding is its ability to simulate problem instances that are otherwise impossible on our hardware due to qubit limitations. Critically, we found that the efficiency of QRAC compression is highly problem-dependent, with sparse interaction graphs yielding a better mapping than dense ones. This thesis provides one of the first empirical investigations into the behavior of QRAC+QAOA for solving combinatorial problems, quantifying the performance trade-offs between compression rate and solution quality. We conclude that while QRAC is a promising direction for extending the reach of NISQ-era quantum optimization, its current form is best suited for moderately sized problems with inherent structural constraints. This work lays the groundwork for future research into more robust encoding strategies and hybrid quantum-classical algorithms.