Improving the efficiency of QAOA using efficient parameter transfer initialization and targeted-single-layer regularized optimization with minimal performance degradation

Technische Samenvatting: Verbeteren van de QAOA-efficiëntie via parametertransfer en gerichte-geregulariseerde optimalisatie

Probleemstelling
Het Quantum Approximate Optimization Algorithm (QAOA) is een belangrijke kandidaat voor het oplossen van combinatorische optimalisatieproblemen (COPs), specifiek het Maximum-Cut (MaxCut) probleem, op nabije quantumapparaten. Echter, QAOA staat voor aanzienlijke uitdagingen naarmate de probleemgrootte ($n$) en de circuitdiepte ($p$) toenemen. Het optimalisatielandschap wordt hoogst niet-convex, gekenmerkt door een exponentieel groeiende oplassingsruimte ($2^n$) en een lineair toenemend aantal parameters ($2p$). Deze complexiteit kan klassieke optimalisatoren doen vastlopen in suboptimale lokale minima, met name voor gewogen grafenfamilies, wat leidt tot slechte benaderingsratio's ($r$). Bovendien is de volledige optimalisatie van alle $2p$ parameters computationeel duur, wat aanzienlijke tijd en middelen vereist, wat de praktische demonstratie van quantumvoordeel belemmert.

Methodologie
De auteurs stellen een hybride strategie voor die parametertransfer-initialisatie combineert met gerichte enkelvoudige-laag optimalisatie en L2-regularisatie om de QAOA-efficiëntie te verbeteren terwijl de prestatieafname wordt geminimaliseerd.

1. Parameter Transfer Initialisatie:

   • De aanpak maakt gebruik van de observatie dat geoptimaliseerde parameters voor vergelijkbare probleeminstanties de neiging hebben te clusteren.
   • Een "donor"-graaf ($G_1$) met een klein aantal knopen ($n_d = 8$) wordt volledig geoptimaliseerd. De initialisatie voor deze donor gebruikt Trotterized Quantum Annealing (TQA) met $t=0.75$, gevolgd door volledige optimalisatie met de Adagrad-optimizer.
   • Deze geoptimaliseerde parameters $\{\gamma^*_i, \beta^*_i\}$ worden overgedragen naar een grotere "acceptor"-graaf ($G_2$) met $n_a \ge n_d$ knopen binnen dezelfde grafenfamilie.

2. Gerichte Enkelvoudige-Laag Optimalisatie:

   • In plaats van alle $2p$ parameters voor de acceptor-graaf opnieuw te optimaliseren, identificeert de methode een specifieke "gerichte" laag ($p_k$) die de beste benaderingsratio oplevert wanneer deze individueel wordt geoptimaliseerd.
   • Voor een vaste diepte $p=15$ hebben de auteurs elke laag $p_k \in [1, 15]$ systematisch getest om de meest waarschijnlijke optimale laag te bepalen voor verschillende grafenfamilies (3-Regular, Erdős–Rényi, Barabási–Albert).
   • Alleen de parameters van deze specifieke laag worden geoptimaliseerd met de COBYLA (Constrained Optimization By Linear Approximation) optimizer, terwijl alle andere lagen op hun overgedragen waarden blijven staan.

3. Regularisatie (L2/Ridge):

   • Om de inconsistentie aan te pakken waarbij gerichte enkelvoudige-laag optimalisatie ($r_s$) incidenteel beter presteert dan volledige optimalisatie ($r_f$) omdat de optimizer tijdens de volledige optimalisatie in een lokaal minimum terechtkomt, introduceren de auteurs L2 (Ridge) regularisatie.
   • Een strafterm $\lambda \sum (\gamma_k^2 + \beta_k^2)$ wordt toegevoegd aan de kostenfunctie. Dit vlakt het oplossingslandschap af, wat de optimizer helpt lokale minima te ontsnappen en de betrouwbaarheid van volledige optimalisatie ($r_f$) verbetert.

Belangrijkste Bijdragen en Resultaten
De studie werd uitgevoerd over drie ongewogen grafenfamilies (3-Regular, Erdős–Rényi, Barabási–Albert) en drie gewogen families, met grafen variërend van 8 tot 24 knopen.

• Prestaties in Ongewogen Grafen:

  • Voor ongewogen 3-Regular (u3R) grafen bereikte de parameter transfer-aanpak een gemiddelde benaderingsratio van 0,9443 voor gerichte enkelvoudige-laag optimalisatie ($r_s$), vergeleken met 0,9551 voor volledige optimalisatie ($r_f$). Dit vertegenwoordigt 98,88% van de optimale prestatie.
  • Cruciaal is dat deze aanpak een 8,06× computationele versnelling opleverde ten opzichte van volledige optimalisatie.
  • Vergelijkbare trends werden waargenomen voor ongewogen Erdős–Rényi (uER) en Barabási–Albert (uBA) grafen, waarbij $r_s$ consistent dicht bij $r_f$ bleef terwijl de optimalisatietijd ($\tau$) aanzienlijk werd verminderd.

• Prestaties in Gewogen Grafen:

  • Gewogen 3-Regular (w3R): De methode presteerde goed, waarbij initialisatie alleen ($r_n$) vaak de Goemans-Williamson klassieke drempel ($r_{GW} \ge 0,878$) overtrof. Gerichte optimalisatie verbeterde deze resultaten verder.
  • Gewogen Erdős–Rényi (wER): De aanpak had moeite met grotere aantallen knopen ($n_a \ge 14$), waarbij $r_s$ onder de $r_{GW}$ drempel zakte. Voor deze complexe gewogen families bleef volledige optimalisatie noodzakelijk om kwalitatief hoogwaardige oplossingen te bereiken.
  • Gewogen Barabási–Albert (wBA): Deze familie vertoonde hybride gedrag; hoewel volledige optimalisatie iets efficiënter was, bleef gerichte optimalisatie een levensvatbaar alternatief.

• Impact van Regularisatie:

  • Zonder regularisatie presteerde gerichte enkelvoudige-laag optimalisatie in 8,92% van de testgevallen beter dan volledige optimalisatie (wat aangeeft dat volledige optimalisatie in een lokaal minimum terechtkwam).
  • De toepassing van L2-regularisatie verminderde deze inconsistentie tot 3,81%, wat de robuustheid van volledige optimalisatie aanzienlijk verbeterde.

• Vergelijking van Optimizer en Initialisatie:

  • Onder diverse optimizers (COBYLA, POWELL, GSLS, NELDER-MEAD, SPSA) werd COBYLA geïdentificeerd als de meest geschikte, die vergelijkbare nauwkeurigheid biedt met de laagste optimalisatietijd.
  • Parameter transfer initialisatie presteerde consequent beter dan TQA en random initialisatie, zowel wat betreft de benaderingsratio als het aantal optimalisatiestappen.

Betekenis en Claims
Het artikel demonstreert dat efficiënte parametertransfer-initialisatie gecombineerd met gerichte enkelvoudige-laag optimalisatie de efficiëntie van QAOA aanzienlijk kan verbeteren met minimale prestatieafname.

De auteurs beweren dat deze strategie effectief de balans vindt tussen nauwkeurigheid en computationele kosten. Door parameters van kleine, volledig geoptimaliseerde instanties over te dragen naar grotere, complexe instanties, biedt de methode een "bijna-optimale" startpositie die de zoekruimte verkleint. De daaropvolgende optimalisatie van een strategisch gekozen enkele laag verfijnt de oplossing verder zonder de exponentiële kosten van volledige heroptimalisatie.

Het werk benadrukt dat hoewel deze aanpak zeer effectief is voor ongewogen en specifieke gewogen grafenfamilies (zoals w3R), het geen universele oplossing is voor alle gewogen topologieën (met name wER), waar de complexiteit van het kostenlandschap nog steeds volledige optimalisatie vereist. De introductie van L2-regularisatie wordt gepresenteerd als een cruciale mitigatiestrategie om het optimalisatielandschap te stabiliseren, waardoor wordt gewaarborgd dat volledige optimalisatie niet minder presteert dan selectieve methoden. Uiteindelijk suggereert de studie een pad om QAOA praktischer te maken voor grootschalige combinatorische problemen door de klassieke computationele overhead die gepaard gaat met parametertuning te verminderen.