⚛️ quantum physics

Quantum Optimization Benchmarking Library - The Intractable Decathlon

Dit artikel introduceert de Quantum Optimization Benchmarking Library (QOBLIB), een collectie van tien uitdagende optimalisatieprobleemklassen die zijn ontworpen om systematische, eerlijke en reproduceerbare benchmarking van kwantumalgoritmen tegenover klassieke solvers mogelijk te maken om de vooruitgang naar kwantumvoordeel bij te houden.

Oorspronkelijke auteurs: Thorsten Koch, David E. Bernal Neira, Ying Chen, Giorgio Cortiana, Daniel J. Egger, Raoul Heese, Narendra N. Hegade, Alejandro Gomez Cadavid, Rhea Huang, Toshinari Itoko, Thomas Kleinert, Pedro Maciel

Gepubliceerd 2026-07-21

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Thorsten Koch, David E. Bernal Neira, Ying Chen, Giorgio Cortiana, Daniel J. Egger, Raoul Heese, Narendra N. Hegade, Alejandro Gomez Cadavid, Rhea Huang, Toshinari Itoko, Thomas Kleinert, Pedro Maciel Xavier, Naeimeh Mohseni, Jhon A. Montanez-Barrera, Koji Nakano, Giacomo Nannicini, Corey O'Meara, Justin Pauckert, Manuel Proissl, Anurag Ramesh, Maximilian Schicker, Noriaki Shimada, Mitsuharu Takeori, Victor Valls, David Van Bulck, Stefan Woerner, Christa Zoufal

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert de meest complexe puzzel ter wereld op te lossen. Je hebt een doos met stukjes die een echt probleem vertegenwoordigen, zoals het plannen van een sporttoernooi, het beheren van een aandelenportefeuille of het routeren van bezorgwagens. Decennialang hebben we vertrouwd op supersnelle klassieke computers om deze stukjes te sorteren. Hoewel deze supercomputers ongelooflijk goed zijn in het snel vinden van goede oplossingen voor veel scenario's, zijn sommige puzzels zo verstrengeld dat het vinden van het perfecte antwoord of het bewijzen van een oplossing als de absoluut beste, een enorme hoeveelheid tijd kost, zelfs voor de krachtigste machines. Ontmoet de quantumcomputer. Zie dit niet als een snellere rekenmachine, maar als een magische ontdekkingsreiziger die de hele puzzellandschap in één keer kan bekijken, waarbij hij tussen mogelijkheden springt op een manier die klassieke machines simpelweg niet kunnen. De grote vraag die wetenschappers nu stellen is: kunnen deze nieuwe quantum-ontdekkingsreizigers deze moeilijke puzzels daadwerkelijk verslaan van de oude supercomputers? Dit gaat niet alleen over het winnen van een race; het gaat over het vinden van een nieuwe manier om problemen op te lossen die momenteel "onhandelbaar" zijn in de zin dat het bewijzen van optimaliteit of het vinden van de absoluut beste oplossing te moeilijk is voor onze huidige technologie om efficiënt te doen.

Dit artikel, getiteld "The Intractable Decathlon," is in essentie een massieve, georganiseerde speeltuin die precies dat wil testen. De auteurs, een enorm team van onderzoekers van universiteiten en techgiganten zoals IBM, hebben een bibliotheek gebouwd genaamd QOBLIB (Quantum Optimization Benchmarking Library). In deze bibliotheek hebben ze tien verschillende soorten "puzzels" (optimalisatieproblemen) geplaatst die berucht moeilijk zijn voor klassieke computers om perfect op te lossen of optimaal te bewijzen, zelfs wanneer de puzzels relatief klein zijn, vaak variërend van minder dan 100 tot ongeveer 100.000 beslissingsvariabelen. Ze noemen deze collectie de "Intractable Decathlon" omdat, net zoals een atletiek decathlon een hardloper test in tien verschillende onderdelen, deze collectie quantumalgoritmen test over tien verschillende soorten uitdagingen.

Het team heeft niet zomaar willekeurige problemen tegen de muur gegooid; ze hebben zorgvuldig tien specifieke categorieën geselecteerd, variërend van Market Split (het verdelen van een groep items in twee gelijke stapels) tot Sports Tournament Scheduling (uitzoeken wie tegen wie speelt en wanneer zonder conflicten). Ze hebben specifieke versies van deze puzzels gemaakt die moeilijk genoeg zijn om de beste huidige klassieke solvers te overrompelen wanneer het gaat om het vinden van de bewijsbaar optimale oplossing, maar klein genoeg zodat huidige quantumcomputers ze daadwerkelijk kunnen aanpakken. Het artikel biedt een "regelboek" voor hoe we meten wie er wint, wat ervoor zorgt dat als een quantumcomputer een puzzel oplost, we precies weten hoe lang het duurde en hoe goed het antwoord was, zodat we het later eerlijk tegen klassieke methoden kunnen vergelijken.

De auteurs hebben ook enkele initiële tests uitgevoerd om een "baseline" vast te stellen, waarbij ze laten zien wat er gebeurt wanneer ze een paar van deze puzzels proberen op te lossen met huidige quantumtools. Ze testten bijvoorbeeld een methode genaamd BF-DCQO op een "Low Autocorrelation Binary Sequence" puzzel (een probleem over het ordenen van een reeks getallen om interferentie te minimaliseren). In deze klassiek gesimuleerde resultaten, die geïdealiseerde runtime-schattingen voor quantumhardware bevatten, vonden ze dat hun quantumbenadering de beste oplossing in een redelijke tijd kon vinden, waarbij het voor bepaalde groottes beter schaalt dan sommige oudere klassieke methoden. Ze zijn echter zeer voorzichtig met de opmerking dat dit nog geen totale overwinning is. Ze geven expliciet aan dat klassieke computers voor veel van deze problemen nog steeds ongelooflijk snel en accuraat zijn in het vinden van goede oplossingen, zelfs als het bewijzen dat ze de beste zijn te lang duurt. Het artikel beweert niet dat quantumcomputers deze problemen hebben "gewonnen" of definitief hebben opgelost; in plaats daarvan suggereert het dat quantummethoden voor specifieke soorten moeilijke puzzels veelbelovend beginnen te zijn en nauwlettend in de gaten gehouden moeten worden.

Het artikel sluit ook de mogelijkheid uit dat we simpelweg elk probleem kunnen nemen en er een quantumalgoritme op kunnen plakken om een magisch resultaat te krijgen. Ze leggen uit dat het omzetten van een echt wereldprobleem naar een formaat dat een quantumcomputer begrijpt (zoals een QUBO) het probleem soms veel groter en moeilijker kan maken, wat een laag van complexiteit toevoegt die eventuele snelheidswinsten teniet kan doen. Ze benadrukken dat we slim moeten zijn over hoe we deze problemen vertalen.

Uiteindelijk is dit artikel een oproep tot actie en een toolkit voor de wetenschappelijke gemeenschap. Het zegt: "Hier zijn tien moeilijke puzzels, hier is hoe we succes meten, en hier is ons eerste poging om ze met quantumtools op te lossen." Het belooft niet dat quantumcomputers morgen de klassieke computers zullen vervangen, maar het biedt de eerste solide, eerlijke grond om de voortgang bij te houden. Door iedereen dezelfde set moeilijke problemen en dezelfde regels voor het meten van resultaten te geven, hopen de auteurs de langzame, gestage klim naar een toekomst te volgen waarin quantumcomputers daadwerkelijk klassieke computers kunnen overtreffen in het oplossen van de meest hardnekkige optimalisatieproblemen uit de wereld.

Technisch Overzicht: De Intractable Decathlon – Een Quantum Optimalisatie Benchmarking Bibliotheek

Probleemdefinitie

Het artikel adresseert de kritieke behoefte aan systematische, eerlijke en vergelijkbare benchmarking van heuristische quantum optimalisatie-algoritmen tegenover state-of-the-art klassieke solvers. Hoewel quantumhardware geavanceerd is tot een punt waar grootschalige benchmarking haalbaar is, ontbeert het veld een gestandaardiseerde set probleeminstanties die tegelijkertijd moeilijk zijn voor klassieke methoden op beheersbare schaal én relevant zijn voor praktische toepassingen.

De auteurs introduceren de Intractable Decathlon, een collectie van tien verschillende combinatorische optimalisatieprobleemklassen. Deze problemen zijn geselecteerd omdat ze:

Moeilijk zijn voor bestaande klassieke solvers (vaak vereist het bewijs van optimaliteit of het vinden van haalbare oplossingen) bij systeemgroottes variërend van minder dan 100 tot ongeveer 100.000 beslissingsvariabelen.
Voornamelijk "primal difficult" zijn, wat betekent dat het vinden van een goede oplossing moeilijk is, wat aansluit bij de capaciteiten van huidige heuristische quantumalgoritmen.
Mappen naar praktisch relevante toepassingen in logistiek, financiën, netwerkontwerp en natuurkunde.
Gemodelleerd kunnen worden met gehele variabelen (bij voorkeur binair) met gehele coëfficiënten, wat numerieke precisieproblemen die gebruikelijk zijn in quantumformuleringen mitigeert.

De tien probleemklassen zijn:

Market Split: Meerdimensionale subset-sum problemen.
Low Autocorrelation Binary Sequences (LABS): Het vinden van binaire sequenties met minimale autocorrelatie.
Minimum Birkhoff Decomposition: Het decomponeren van dubbel stochastische matrices in het minimum aantal permutatiematrices.
Steiner Tree Packing: Het verpakken van knoop-disjuncte Steiner-bomen in een graaf.
Sports Tournament Scheduling: Het plannen van double round-robin toernooien met complexe restricties.
Portfolio Optimization: Multi-periode gemiddelde-variantie optimalisatie met transactiekosten.
Maximum Independent Set (MIS): Het vinden van de grootste verzameling niet-aangrenzende vertices in een graaf.
Network Design: Het construeren van gerichte grafen om de maximale randbelasting te minimaliseren.
Vehicle Routing Problem (CVRP): Capacitated vehicle routing met een vaste vlootgrootte.
Topology Design: Het minimaliseren van de netwerkdiameter gegeven orde- en graadrestricties (Order Degree Problem).

Methodologie

De auteurs stellen een model-onafhankelijk benchmarking framework voor om maximale flexibiliteit te bieden in de keuze van algoritmen, modellen en hardwareplatforms. De methodologie omvat:

1. Probleemformulering en Modellering

Focus op Hele Getallen: Problemen worden gedefinieerd over gehele beslissingsvariabelen $x \in \mathbb{Z}^n$ met lineaire of kwadratische objectieven en restricties. Coëfficiënten worden geschaald naar gehele getallen om numerieke onnauwkeurigheden te voorkomen.
Model-Agnosticisme: Hoewel de bibliotheek standaard Mixed Integer Programming (MIP) en Quadratic Unconstrained Binary Optimization (QUBO) formuleringen biedt, is het doel van de benchmarking niet gebonden aan een specifieke formulering. Dit erkent dat het herformuleren van een probleem (bijv. van ILP naar QUBO) de probleemgrootte en dichtheid drastisch kan veranderen, wat potentieel nieuwe uitdagingen of voordelen voor specifieke solvers introduceert.
Haalbaarheid vs. Optimalisatie: Het framework maakt onderscheid tussen haalbaarheidsproblemen (het vinden van elke geldige oplossing) en optimalisatieproblemen (het vinden van de beste oplossing). Gezien het feit dat de meeste quantumalgoritmen heuristieken zijn zonder garanties op optimaliteit, focust de benchmark op het vinden van hoogwaardige haalbare oplossingen in plaats van het bewijzen van globale optimaliteit.

2. Metrieken en Rapportage

Om reproduceerbaarheid en vergelijkbaarheid te garanderen, definiëren de auteurs specifieke metrieken:

Oplossingskwaliteit: Beste objectieve waarde gevonden over herhalingen. Voor stochastische algoritmen wordt het aantal succesvolle runs (het vinden van een oplossing binnen een tolerantie $\epsilon$ van de best gevonden oplossing) gerapporteerd.
Computationele Bronnen:
- Totale Runtime: Wandkloktijd exclusief wachtrij/idle tijd.
- Hardware Breakdown: Scheiding van de tijd besteed aan CPU's, GPU's, Quantum Processing Units (QPU's) en andere hardware.
- Definitie van Quantum Runtime: Specifiek gedefinieerd voor het IBM Quantum Platform als de tijd van ontvangst van de payload tot extractie van samples, inclus inclusief circuitvoorbereiding en executie, maar exclusief klassieke transpilatie tijd (die aan pre-processing wordt toegeschreven).
Richtlijnen voor Indiening: Een gestandaardiseerd sjabloon (Tabel 10) wordt geleverd voor de Quantum Optimization Benchmarking Library (QOBLIB) om ervoor te zorgen dat alle noodzakelijke details (modelleringsaanpak, variabelenaantallen, bereik van coëfficiënten, workflow stappen) worden vastgelegd.

3. Instantie Generatie

De bibliotheek bevat instanties die gegenereerd zijn om "primal difficult" te zijn. Voor problemen waarbij het vinden van een haalbare oplossing triviaal is, worden instanties geconstrueerd door reverse-engineering vanuit bekende oplossingen om moeilijkheid te garanderen. De instanties variëren in dichtheid, bereik van coëfficiënten en variabelenaantallen om verschillende algoritmische bottlenecks te testen.

Belangrijkste Bijdragen

De QOBLIB Repository: Een open-source bibliotheek met probleeminstanties, modellen (MIP/QUBO), solution checkers en baseline resultaten.
De Intractable Decathlon: Een gecureerde set van tien probleemklassen die de kloof overbruggen tussen theoretische hardheid en praktische relevantie, specifiek geselecteerd om uitdagend te zijn voor klassieke solvers op schalen die toegankelijk zijn voor nabije quantumhardware.
Gestandaardiseerd Benchmarking Protocol: Een rigoureus pakket aan definities voor metrieken, runtime meting (vooral voor quantumhardware) en rapportageformaten om een eerlijke vergelijking tussen verschillende quantum en klassieke benaderingen te faciliteren.
Baseline Resultaten: Het artikel levert uitgebreide klassieke baseline resultaten met behulp van state-of-the-art solvers (bijv. Guroo, CPLEX, gespecialiseerde heuristieken) om prestatie-ondergrenzen vast te stellen. Het presenteert ook illustratieve quantum baseline resultaten voor drie specifieke problemen met behulp van verschillende quantumalgoritmen.

Resultaten en Illustratieve Voorbeelden

Het artikel presenteert klassieke baselines voor alle tien de probleemklassen, waarbij wordt aangetoond dat veel instanties momenteel onoplosbaar zijn tot bewezen optimaliteit door klassieke solvers binnen een redelijke tijd, of aanzienlijke computationele middelen vereisen.

Illustratieve Quantum Baselines:
De auteurs bieden voorlopige resultaten voor drie probleemklassen met behulp van specifieke quantumalgoritmen om de indieningsvorm en huidige capaciteiten te demonstreren:

Low Autocorrelation Binary Sequences (LABS):
- Algoritme: Bias-field Digitized Counter-Diabatic Quantum Optimization (BF-DCQO).
- Resultaat: Op een sequentielengte van $n=20$ (wat de vorige quantum implementaties van $n=18$ overtreft), vond het algoritme optimale oplossingen op het ibm marrakesh device. De gemiddelde runtime was ~61 seconden (inclusief pre/post-processing), met een QPU runtime van ~60,8 seconden.
- Vergelijking: De schaling van BF-DCQO was vergelijkbaar met QAOA met $p=12$ lagen, maar vereiste zes keer minder entangling gates. Het presteerde beter dan exacte klassieke solvers (Guroo, CPLEX) in time-to-solution voor de specifieke geteste instantie, hoewel de klassieke solvers uiteindelijk optimale oplossingen vonden voor kleinere instanties.
Minimum Birkhoff Decomposition:
- Algoritme: Variational Quantum Algorithm (VQA) gebruikmakend van een geparametriseerd quantumcircuit om permutatiematrices te samplen.
- Resultaat: Getest op $n=4$ en $n=5$ dubbel stochastische matrices. Voor $n=4$ vond het algoritme consistent exacte decomposities met 3–4 permutaties, wat de klassieke benaderende solvers (Birkhoff+, Blended FW) evenaart of overtreft. Voor $n=5$ degradeerde de prestatie, waarbij slechts enkele instanties een ijle (sparse) decompositie bereikten, wat de huidige beperkingen van variational benaderingen op grotere, complexere instanties benadrukt.
Maximum Independent Set (MIS):
- Algoritme: Heuristische solver (ABS2) op GPU-hardware.
- Resultaat: Leverde baseline prestatiegegevens voor grafen tot 4000 knopen, waarbij het gat tussen heuristische oplossingen en optimale grenzen werd getoond, dienend als doelwit voor quantum heuristieken.

Betekenis en Claims

Het artikel claimt dat de QOBLIB en de Intractable Decathlon de noodzakelijke infrastructuur bieden om verder te gaan dan component-niveau benchmarking (bijv. gate fidelity) naar applicatie-niveau benchmarking.

Demonstreren van Quantum Voordeel: De auteurs stellen dat alleen door probleeminstanties op te lossen die moeilijk zijn voor klassieke computers (primal difficulty), een echt quantumvoordeel kan worden aangetoond. De geselecteerde instanties zijn ontworpen om intratabel te zijn voor klassieke solvers op de schaal waarop nabije quantumapparaten kunnen opereren.
Community Samenwerking: Het werk wordt geframed als een oproep tot actie voor de optimalisatiegemeenschap om deze instanties te gebruiken om de voortgang in algoritmen, software en hardware bij te houden.
Bescheidenheid over Huidige Capaciteiten: Het paper is bescheiden over de huidige quantumprestaties. Het erkent dat hoewel quantumalgoritmen veelbelovend zijn qua schaling en specifieke instanties (zoals LABS $n=20$ ), ze nog niet consistent de beste klassieke heuristieken over de hele linie overtreffen. Het primaire doel is het vaststellen van een gestandaardiseerde vorm om benchmarking-oplossingen te presenteren, wat zorgt voor vergelijkbaarheid, reproduceerbaarheid en de mogelijkheid om verbeteringen in de loop van de tijd te volgen.

De auteurs concluderen dat dit framework essentieel is voor het verifiëren van algoritmische correctheid, het identificeren van bottlenecks en uiteindelijk het bepalen of quantumcomputers een praktisch voordeel kunnen bieden bij het oplossen van echte combinatorische optimalisatieproblemen.