Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice

Titel: Benchmarking Variational Quantum Algoritmen voor Combinatorische Optimalisatie in de Praktijk

Auteurs: Tim Schwägerl et al.
Datum: 7 augustus 2024

1. Probleemstelling

Combinatorische optimalisatie (CO) is een fundamenteel probleem in industrie en wetenschap (bijv. logistiek, chipontwerp, deeltjestracking), waarbij een optimale oplossing moet worden gevonden uit een eindige verzameling mogelijkheden. Veel CO-problemen zijn NP-hard, wat betekent dat ze niet efficiënt opgelost kunnen worden door klassieke of quantumcomputers in het algemeen.

In het huidige tijdperk van Noisy Intermediate-Scale Quantum (NISQ) computers worden Variational Quantum Algorithms (VQA's), zoals de Variational Quantum Eigensolver (VQE) en Quantum Approximate Optimization Algorithm (QAOA), voorgesteld als een oplossing. Deze hybride algoritmen gebruiken een klassieke optimizer om de parameters van een quantumcircuit (ansatz) te trainen.

Het kernprobleem: Hoewel VQA's theoretisch veelbelovend zijn, vereist het trainen van deze circuits vaak een aantal resources (samples/evaluaties) dat superpolynomiaal schaalt met de probleemgrootte. Bestaande benchmarks zijn vaak beperkt tot "proof-of-principle" demonstraties zonder realistische resource-beperkingen. Het is onduidelijk wat deze schalingsresultaten in de praktijk betekenen voor het oplossen van kleine CO-problemen.

2. Methodologie

De auteurs voeren uitgebreide numerieke experimenten uit om de prestaties van een VQE te vergelijken met klassieke baselines onder strikte resource-beperkingen.

• Benchmarkprobleem: Het Max-Cut-probleem op willekeurige 3-reguliere grafen. De probleemgroottes variëren van $N=11$ tot $N=61$ variabelen.
• Algoritmen vergeleken:
  1. VQE (Variational Quantum Eigensolver): Een hybride algoritme met een "hardware-efficient" circuit (RY-rotaties en een bakstenen patroon van CNOT-gates).
     • Cost Function: Conditional Value at Risk (CVaR) met $\gamma=0.1$ om de kans op hoge oplossingskwaliteit te maximaliseren.
     • Optimizer: COBYLA (gradient-free).
     • Resources: Maximaal $10^6$ evaluaties van de objectiefunctie ($N_{iter} \times N_{shots}$).
  2. Sampling with Replacement: Willekeurig genereren van computatie-basistoestanden. Dit dient als een ondergrens om te testen of de VQE meer doet dan alleen "gokken".
  3. Greedy Algorithm: Een klassiek heuristisch algoritme dat lokaal de objectiefunctie maximaliseert door bit-flips.
• Vergelijkingsstrategie:
  • De VQE en de Greedy-algoritme worden gestart vanuit dezelfde initiële punten. Voor de VQE is dit de initiële parameterinstelling; voor de Greedy-algoritme wordt een toestand gegenereerd door het quantumcircuit eenmaal te draaien met diezelfde parameters.
  • De prestaties worden gemeten op basis van het benaderingsratio ($\alpha$) en de succeskans (voor kleine problemen).
  • Er wordt gebruik gemaakt van binned statistics om de correlatie tussen de prestaties van de algoritmen per instantie te analyseren.

3. Belangrijkste Bijdragen

1. Realistische Resource-Benchmarking: In plaats van alleen theoretische snelheidswinst te beloven, analyseren de auteurs de prestaties binnen een vast, realistisch budget van $10^6$ evaluaties.
2. Definitie van een "Minimum Probleemgrootte": Het identificeren van het punt waarop quantumalgoritmen beginnen om willekeurig sampling te overtreffen.
3. Correlatie-analyse: Het onderzoeken of goede startpunten voor een VQE ook goede startpunten zijn voor klassieke heuristieken (Greedy), wat inzicht geeft in de onderliggende mechanismen.
4. Nieuwe Metriek: Het introduceren van een methode om de kans te berekenen dat algoritme A beter presteert dan algoritme B, gebaseerd op Wilson-score intervallen, in plaats van alleen op het gemiddelde verschil.

4. Resultaten

De resultaten tonen een duidelijk onderscheid afhankelijk van de probleemgrootte:

• Kleine Probleemgroottes ($N \le 21$):

  • De VQE presteert slechter dan willekeurig sampling en de Greedy-algoritme.
  • Voor $N=11$ is de oplossingruimte zo klein dat willekeurig sampling al zeer hoge benaderingsratio's levert; de VQE kan hier niet concurreren.
  • De VQE valt vaak in lokale minima en heeft te weinig resources om te convergeren naar een betere oplossing dan random guessing.

• Grote Probleemgroottes ($N > 30$):

  • De VQE begint beter te presteren dan willekeurig sampling. Voor $N=31$ overtreft de VQE sampling in ongeveer 95% van de gevallen.
  • De VQE overtreft ook de Greedy-algoritme, maar dit gebeurt pas na een aanzienlijk aantal iteraties (bijv. ~100 iteraties voor $N=31$, tot ~600 voor $N=61$).
  • De Greedy-algoritme convergeert zeer snel naar lokale minima, maar de VQE kan uiteindelijk (na meer resources) betere lokale minima vinden.

• Schaalbaarheid van het Voordeel:

  • Het absolute voordeel van de VQE ten opzichte van de Greedy-algoritme neemt af naarmate de probleemgrootte toeneemt (van ~0.025 bij $N=31$ naar ~0.005 bij $N=61$).
  • Het aantal evaluaties dat nodig is om dit maximale voordeel te bereiken, neemt echter monotoon toe met de probleemgrootte.

• Correlatie:

  • Er is een zwakke correlatie tussen de prestaties van de VQE en sampling (afhankelijk van de probleemgrootte).
  • Er is geen correlatie tussen de prestaties van de VQE en de Greedy-algoritme. Dit suggereert dat ze fundamenteel verschillende mechanismen gebruiken; een goed startpunt voor de VQE garandeert geen goed startpunt voor de Greedy-algoritme.

5. Betekenis en Conclusie

De studie concludeert dat variational quantum algoritmen voor combinatorische optimalisatie niet overal superieur zijn aan klassieke methoden, zelfs niet in het NISQ-tijdperk.

• Kritieke drempel: Er is een minimum probleemgrootte (rond 30 variabelen in dit specifieke setup) nodig voordat de VQE een praktisch voordeel heeft ten opzichte van simpele sampling. Voor kleinere problemen zijn klassieke methoden (of zelfs random sampling) superieur.
• Resource-efficiëntie: Het trainen van VQA's vereist een enorme hoeveelheid resources om het punt te bereiken waar ze klassieke heuristieken (zoals Greedy) overtreffen.
• Toekomstperspectief: De auteurs benadrukken dat benchmarks moeten worden uitgevoerd met realistische resource-beperkingen. Ze suggereren dat hun benchmarks uitgebreid kunnen worden naar fysieke problemen (zoals het meten van observabelen) waar klassieke methoden zoals Markov Chain Monte Carlo (MCMC) als baseline kunnen dienen.

Kortom, dit werk levert een noodzakelijke "realiteitscheck" voor het veld van quantum optimalisatie, waarbij wordt aangetoond dat quantumvoordeel niet vanzelfsprekend is en sterk afhankelijk is van de probleemgrootte en de beschikbare resources.