Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-12366
Authors: Obst, Julian
Title: Parameter initialization for warm-starting QAOA
Issue Date: 2022
metadata.ubs.publikation.typ: Abschlussarbeit (Master)
metadata.ubs.publikation.seiten: 70
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-123850
http://elib.uni-stuttgart.de/handle/11682/12385
http://dx.doi.org/10.18419/opus-12366
Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for achieving quantum advantage on near-term quantum devices. Warm-Started QAOA (WS-QAOA) is animproved version of QAOA. It utilizes an approximate solution to the problem in question, which is efficiently computed on classical hardware first. This version aims for improved performanceat a lower depth. Since QAOA is a variational algorithm, finding suitable parameters is key to its successful application. Oftentimes, good parameters are obtained by picking random initial parameters and optimizing them. There have been recent works that demonstrated a successful transfer of parameters between different problem instances solved with QAOA. This thesis investigates how parameter transfer can be applied to WS-QAOA for MaxCut with a focus on unweighted 3-, 4- and 5-regular graphs. I show that parameters can be successfully transferred between warm-started d-regular instances, where both instances have degree d. The approximate MaxCut solution used to warm-start the algorithm (initial cut) greatly influences the success and a successful transfer is more likely if both instances are warm-started with a good initial cut. Further, I show empirically that for WS-QAOA the regular instances also demonstrate a concentration of good parameters. For example, in the experiments performed here, optimized parameters of a regular instance could be transferred to another with no significant reduction in approximation ratio on average. The 3- and 5-regular instances even showed an increase of the average approximation ratio by 0.003 and 0.008 respectively, 4-regular instances saw a 0.041 decrease. However, this had more to do with the quality of the initial cut than the transferred parameters. These insights lead to an approach called landscape approximation that helps to determine good initial parameters that can be used directly or be further optimized.
Der Quantum Approximate Optimization Algorithm (QAOA) ist ein vielversprechender Kandidat für Quantenüberlegenheit auf Near-Term-Hardware. Warm-started QAOA (WS-QAOA) ist eine verbesserte Version von QAOA. Diese nutzt für das vorliegende Problem eine vorberechnete approximative Lösung, welche effizient auf klassischer Hardware bestimmt wird. Diese Version zielt auf bessere Ergebnisse bei geringer Tiefe ab. Da es sich bei QAOA um einen variationellen Algorithmus handelt, ist das Finden von passenden Parametern entscheidend für dessen erfolgreiche Anwendung. Oft werden gute Parameter bestimmt, indem zufällig gewählte initiale Parameter optimiert werden. Aktuelle Arbeiten demonstrierten die erfolgreiche Übertragung von Parametern zwischen verschiedenen Probleminstanzen, die mit QAOA gelöst wurden. Diese Thesis untersucht, wie die Übertragung von Parametern auf WS-QAOA für MaxCut mit einem Fokus auf 3-, 4- und 5-reguläre Graphen angewendet werden kann. Ich zeige, dass eine Übertragung zwischen warm-started d-regulären Instanzen erfolgreich sein kann, wobei beide Instanzen den Grad d haben. Die Näherungslösung des MaxCut-Problems (der sog. initiale Schnitt), welche für den Warm-Start des Algorithmus eingesetzt wird, hat hierbei einen großen Einfluss auf den Erfolg, und eine erfolgreiche Übertragung ist wahrscheinlicher, wenn beide Instanzen einen guten initialen Schnitt haben. Weiter zeige ich empirisch, dass die regulären Instanzen bei WS-QAOA eine Konzentration von guten Parametern aufweisen. Zum Beispiel konnten in den hier durchgeführten Experimenten optimierte Parameter einer regulären Instanz an eine weitere übertragen werden, ohne dass dabei die durchschnittliche Näherungsgüte signifikant reduziert wurde. Die 3- und 5-regulären Instanzen zeigten dabei sogar einen Zuwachs der Güte von 0.003 bzw. 0.008, während die 4-regulären Instanzen eine Reduzierung um 0.041 aufwiesen. Dies hatte mehr mit der Qualität des initialen Schnitts als mit den übertragenen Parametern zu tun. Diese Erkenntnisse führten zu einem Verfahren, genannt Landscape Approximation, welches dabei helfen kann, gute initiale Parameter zu bestimmen, die direkt benutzt werden können oder als Initialisierung der Optimierung dienen.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
MA_Obst_final.pdf4,82 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.