title: Integer Optimization for Quantum Computing
title: Ganzzahlige Optimierung für Quantencomputing
Creators: name: Wagner, Friedrich
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2024

description: Integer optimization problems arise in various fields of everyday life. Although being NP-hard in general, modern algorithms routinely solve even very large instances in reasonable time. Nonetheless, there exist practically relevant problems which are intractable for state-of-the-art integer optimization methods. As a result, recent progress in quantum computing hardware and the discovery of quantum algorithms with provable complexity advantages has motivated researchers to develop quantum approaches for such problems. However, exact quantum algorithms for integer optimization by far exceed the capabilities of existing quantum hardware. Therefore, researchers focus on quantum heuristics, which are less hardwaredemanding than exact approaches. It remains open whether future quantum algorithms and hardware will outperform their classical counterparts. Currently, the size limitation and noise vulnerability of existing quantum devices hinder the scalability of quantum heuristics towards practically relevant problem sizes. Moreover, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. This thesis aims at bringing quantum computation closer to practical utility. The first part of this thesis combines the potentials of near-future quantum and classical techniques for integer optimization. We do so by developing two hybrid quantum-classical algorithms for combinatorial optimization problems, which can handle significantly larger instances than pure quantum approaches. In the first hybrid algorithm, we integrate a quantum subroutine in an exact integer optimization method for vehicle routing. This allows us to solve the vehicle routing problem to proven optimality despite the heuristic nature of the underlying quantum algorithm. Our hybrid method cleverly exploits the inherent randomness of quantum algorithms since the classical part benefits from the diversity of solutions returned by the quantum subroutine. Moreover, we develop an improved model for the subproblem, which shows increased performance on quantum hardware compared to existing modeling approaches. The second hybrid algorithm heuristically solves the NP-hard problem of quadratic unconstrained binary optimization. The proposed heuristic employs a linear programming relaxation, which can be computed efficiently. This fact renders our heuristic well-suited for an integration into exact branch-andcut algorithms. For instances too large for quantum hardware, we reduce the problem size according to a linear relaxation solution such that the reduced problem can be handled by quantum machines of limited size. The reduced problem is then solved via QAOA, a well-known parameterized quantum algorithm. In this context, we improve the runtime of QAOA considerably by deriving optimal parameters for special instances which further motivates a high-quality parameter estimate for arbitrary instances. We intensively evaluate both proposed algorithms on actual quantum hardware. Due to the problem decomposition, we are able to solve instances which are an order of magnitude larger than the capabilities of existing quantum hardware, highlighting the advantages of our hybrid approaches compared to pure quantum algorithms. In the second part of this thesis, we utilize integer optimization techniques to improve the execution of algorithms on limited quantum hardware. More specifically, we optimize the compilation of quantum algorithms. When compiling quantum algorithms onto specific hardware, an NP-hard combinatorial optimization problem, known as qubit routing, needs to be solved. Our approach decomposes the qubit routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. We formulate the allocation subproblem as a binary program and strengthen its linear relaxation by deriving several classes of novel valid inequalities, speeding-up the solution significantly. For the token swapping part, we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. The overall qubit routing solutions are obtained fast and are typically close to optimal. Moreover, we provide a way to efficiently measure and integrate hardware-specific noise characteristics in our compilation method. As a result, the measurement effort is minimized and the compiled quantum algorithms are resilient to noise-induced errors. We extensively evaluate our compilation methods on QAOA executed on actual quantum hardware. Our results show a significant increase in solution quality in comparison to standard compilation methods. In summary, this work sheds light on the potentials and challenges of near-future quantum computing for optimization.
description: Ganzzahlige Optimierungsprobleme treten vielfältig im Alltag auf. Obwohl diese im allgemeinen NPschwer sind, lösen moderne Algorithmen selbst sehr große Instanzen routiniert und in akzeptabler Zeit. Nichtsdestotrotz existieren praxisrelevante Probleme, welche sogar mit modernsten Techniken nicht exakt gelöst werden können. Deshalb hat der Fortschritt in Quantencomputing-Hardware und Algorithmentheorie Forscher motiviert, Quantenalgorithmen für derartige Probleme zu entwickeln. Jedoch übersteigen exakte Quantenalgorithmen für ganzzahlige Optimierungsprobleme die Kapazitäten existierender Quantenhardware bei Weitem. Deshalb fokussieren sich Wissenschaftler auf die Entwicklung von Quantenheuristiken, die geringere Anforderungen an die Hardware stellen als exakte Verfahren. Es ist ungeklärt, ob zukünftige Quantenalgorithmen und -hardware ihre klassischen Gegenstücke übertreffen werden, denn die limitierte Größe und Rauschanfälligkeit aktueller Quantenhardware verhindert eine Skalierung von Quantenheuristiken hin zu praxisrelevanten Problemgrößen. Weiterhin sind klassische, exakte Methoden, wie ganzzahlige Programmierung, für beweisbare Optimalität unumgänglich. Das Ziel dieser Arbeit ist es, die Praxistauglichkeit aktueller Quantenrechner zu verbessern. Der erste Teil dieser Arbeit kombiniert die Potenziale von Quanten- und klassischen Algorithmen für kombinatorische Optimierung. Dazu entwickeln wir zwei quanten-klassisch hybride Ansätze. Der erste dieser Algorithmen integriert eine Quantensubroutine in eine klassische, exakte Methode der ganzzahligen Optimierung für Tourenplanungsprobleme. Obgleich die Quantensubroutine von heuristischer Natur ist, erlaubt der hybride Ansatz eine exakte Lösung des Tourenplanungsproblems. Weiterhin nutzt dieser den inhärenten Zufall von Quantenalgorithmen geschickt aus, da der klassische Teil von Diversität in Lösungen zum Subproblem profitiert. In diesem Zusammenhang entwickeln wir ein Modell für das Subproblem, welches von geringerer Dimension und weniger dicht besetzt ist als existierende Modellierungsansätze und deshalb auf aktueller Quantenhardware bessere Ergebnisse liefert. Der zweite hybride Algorithmus stellt eine Heuristik für das generische, NP-schwere Problem der binär-quadratischen, unrestringierten Optimierung dar. Diese Heuristik basiert auf einer linearen Relaxierung, die effizient berechnet werden kann. Dadurch eignet sich der hybride Algorithmus besonders zur Integration in exakte Branch-and-Cut-Algorithmen. Instanzen, die zu groß für aktuelle Quantenrechner sind, werden anhand einer Relaxierungslösung verkleinert, sodass sie von Quantenrechnern begrenzter Größe bearbeitet werden können. Das reduzierte Problem wird anschließend durch QAOA, einem bekannten, parametrierten Quantenalgorithmus, gelöst. In diesem Zusammenhang verbessern wir die Laufzeit von QAOA signifikant, indem wir optimale Parameter für spezielle Instanzen, sowie eine hochqualitative Parameterschätzung für beliebige Instanzen herleiten. Wir evaluieren beide hybride Algorithmen intensiv auf realen Quantenrechnern. Durch die Problemdekomposition können wir Instanzen lösen, deren Größe die Kapazität vorhandener Quantenhardware um eine Größenrodung übersteigt. Der zweite Teil dieser Arbeit entwickelt Techniken der ganzzahligen Optimierung, die die Ausführung von Algorithmen auf limitierten Quantenrechnern verbessern. Insbesondere optimieren wir die Kompilierung von Quantenalgorithmen. Beim Kompilierungsprozess tritt ein NP-schweres, kombinatorisches Optimierungsproblem auf, welches als Qubit-Routing bekannt ist. Unser Ansatz dekomponiert dieses Routingproblem in ein Allokationsproblem und eine Menge an Token-Swapping-Problemen. Dadurch können wir den Allokations- und den Token-Swapping-Teil getrennt angehen. Wir formulieren das Allokationsproblem als ein binäres Programm und verstärken seine lineare Relaxierung durch mehrere Klassen an neuartigen Schnittebenen. Dies beschleunigt das Lösen des Allokationsproblems signifikant. Für die Token-Swapping-Probleme entwickeln wir einen exakten Branch-and-Bound-Ansatz. In diesem Zusammenhang verbessern wir bekannte untere Schranken an das Token-Swapping-Problem. Des Weiteren verbessern wir einen existierenden Approximationsalgorithmus für das Token-Swapping-Problem, welcher wesentlich schneller als der exakte Branch-and-Bound-Ansatz ist und dennoch hochqualitative Lösungen liefert. Auch der Gesamtalgorithmus generiert schnell nahezu optimale Lösungen. Weiterhin entwickeln wir eine Methode, die Rausch-Charakteristika von Quantenrechnern effizient zu messen und in den Kompilierungsalgorithmus zu integrieren. Dadurch wird der Messaufwand minimiert sowie die Fehleranfälligkeit der kompilierten Quantenalgorithmen erheblich reduziert. Wir evaluieren unsere Kompilierungsmethode umfassend durch Ausführen von QAOA auf realen Quantenrechnern. Die Ergebnisse zeigen eine signifikante Verbesserung der Lösungsqualität im Vergleich zu Standardmethoden zur Kompilierung. Zusammenfassend zeigt diese Arbeit Potentiale und Herausforderungen auf, die im aktuellen Quantencomputing für Optimierung auftreten.