Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

Technische Samenvatting: Evaluatie van de Nauwkeurigheid en Prestaties van Quantum-, Klassieke en Hybride Solvers voor het Max-Cut Probleem

Probleemdefinitie
Deze studie behandelt het NP-harde Max-Cut probleem en de equivalente formulering ervan, het Quadratic Unconstrained Binary Optimization (QUBO) probleem. Het doel is om de knopen van een gewogen ongerichte graaf te verdelen in twee disjuncte verzamelingen zodanig dat de som van de gewichten van de randen die de verzamelingen verbinden, wordt gemaximaliseerd. De paper evalueert het vermogen van diverse solvers om oplossingen te vinden die dicht bij het globale optimum liggen, waarbij wordt erkend dat voor grote instanties exacte oplossingen vaak computationeel onhaalbaar zijn, wat het gebruik van benaderende heuristieken noodzakelijk maakt.

Methodologie en Experimentele Opstelling
De auteurs hebben een uitgebreide benchmarkingstudie uitgevoerd met behulp van drie verschillende datasets bestaande uit 139 probleeminstanties met groottes variërend van 100 tot 10.000 knopen.

• Datasets:
  1. Billionnet en Elloumi (be): 50 instanties met $n \in \{101, 121, 151\}$. Globale optima werden berekend met behulp van exacte solvers zoals BiqBin en MADAM.
  2. Beasley collectie (bqp): 20 instanties met $n \in \{251, 501\}$. Optima voor $n=251$ werden exact berekend; voor $n=501$ werden de best bekende waarden uit de literatuur gebruikt.
  3. G-dataset (G): 69 instanties met $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$. Globale optima zijn onbekend; de best bekende oplossingen uit de literatuur werden gebruikt als benchmarks.
• Geëvalueerde Solvers:
  • Quantum Annealing (QPU): D-Wave Advantage systeem dat gebruikmaakt van een "fast annealing" functie om qubits te isoleren van omgevingseffecten. Beperkt tot instanties met $n \le 151$.
  • Hybride Solver: D-Waves cloud-gebaseerde "LeapHybridSampler", die iteratief klassieke methoden (interruptible simulated annealing, tabu search, parallel tempering) combineert met QPU-aanroepen. In staat om alle instantiegroottes aan te kunnen.
  • Klassieke Simulated Annealing (SA): Twee varianten van het algoritme uit [3] zijn geïmplementeerd:
    • SA1: Agressieve stapgrootte, initiële temperatuur 10.000 (geoptimaliseerd voor een runtime vergelijkbaar met de QPU).
    • SA2: Conservatieve stapgrootte, initiële temperatuur 40.000 (geoptimaliseerd voor de kwaliteit van de oplossing).
  • Simulated Bifurcation Machine (SBM): Toshiba's hardware solver. Resultaten zijn overgenomen uit bestaande literatuur [4], aangezien de auteurs geen directe toegang hadden tot de solver.

Belangrijkste Resultaten

• Kleine Instanties ($n \le 151$): De hybride solver en beide SA-varianten (SA1, SA2) bereikten consistent het globale optimum voor alle instanties. De QPU produceerde echter consequent oplossingen die significant ver verwijderd waren van het globale optimum.
• Medium Instanties ($n = 251, 501$): De hybride solver en SA-varianten bereikten opnieuw de globale optima (voor $n=251$) of de best bekende waarden (voor $n=501$). De QPU kon niet worden getest vanwege capaciteitsbeperkingen.
• Grote Instanties ($n \ge 800$):
  • Oplossingskwaliteit: De SBM en SA2 produceerden de hoogste kwaliteit oplossingen en vonden vaak de best bekende waarden. De hybride solver presteerde merkbaar slechter dan SBM en SA2, terwijl SA1 de laagste kwaliteit oplossingen produceerde van de geteste methoden.
  • Computationele Tijd: De hybride solver en SBM vertoonden efficiënte computationele tijden (seconden tot tientallen seconden). SA2 had aanzienlijk meer tijd nodig (honderden seconden, ongeveer 1000x trager dan Hybrid/SBM in sommige vergelijkingen) om een superieure oplossingskwaliteit te bereiken. SA1 had een runtime die vergelijkbaar was met de hybride solver, maar leverde inferieure oplossingen op.

Betekenis en Claims
De paper beweert het begrip van quantum-ondersteunde optimalisatie te vergroten door de nieuwe D-Wave fast annealing QPU en de hybride solver rigoureus te testen tegen state-of-the-art klassieke methoden op een gestandaardiseerde, publiekelijk beschikbare set van Max-Cut instanties.

De auteurs concluderen dat:

1. QPU Beperkingen: De D-Wave QPU, zelfs met fast annealing, faalt in het vinden van optimale oplossingen voor de geteste instanties en is beperkt door de probleemgrootte ($n \le 151$).
2. Effectiviteit van Hybride Solvers: De D-Wave hybride solver is zeer efficiënt qua snelheid en schaalbaarheid (het afhandelen van tot 10.000 knopen) en produceert bijna optimale oplossingen voor kleinere instanties. Echter, voor de grootste instanties wordt deze overtroffen in oplossingskwaliteit door klassieke SA (specifiek de SA2-variant) en SBM.
3. Concurrentiekracht van Klassieke Methoden: Transparante, klassieke simulated annealing algoritmen (met name de SA2-variant) blijven zeer competitief en presteren vaak beter dan de black-box hybride solver wat betreft oplossingskwaliteit, zij het tegen een hogere computationele kosten.
4. Transparantiekloof: De auteurs uiten hun frustratie over het "black-box" karakter van de hybride solver, waarbij zij opmerken dat het gebrek aan inzicht in de interne workflow en het gebruik van quantumbronnen wetenschappelijke analyse belemmert.

De studie claimt geen quantumvoordeel voor de specifieke solvers en probleeminstanties die zijn getest; in plaats daarvan benadrukt het dat voor Max-Cut huidige klassieke heuristieken (wanneer afgestemd op kwaliteit) en gespecialiseerde hardware zoals SBM de prestaties van de geteste quantum- en hybride benaderingen kunnen evenaren of overtreffen.