QUBO: hoe computers de beste combinatie uit miljarden mogelijkheden zoeken
Stel je organiseert een groot bruiloftsfeest en moet gasten over tafels verdelen. Elke gast krijgt een simpele ja/nee-keuze per tafel: zit hij er wel of niet. Maar de kwaliteit van je indeling hangt niet alleen af van losse keuzes, want twee ruziemakende families naast elkaar zetten is rampzalig, terwijl twee beste vrienden samen zetten juist fijn is. De beste oplossing hangt dus af van combinaties van keuzes, niet van iedere keuze apart. QUBO is precies dat soort probleem in wiskundige vorm: een manier om vraagstukken met alleen ja/nee-beslissingen te beschrijven, waarbij de 'kosten' ontstaan uit de interactie tussen paren van beslissingen.
De afkorting staat voor Quadratic Unconstrained Binary Optimization, in het Nederlands zoiets als 'kwadratische onbeperkte binaire optimalisatie'. Het is geen apparaat of technologie op zichzelf, maar een wiskundig format: een standaardmanier om lastige keuzevraagstukken te noteren zodat computers, en sinds een jaar of tien ook kwantumcomputers, ze kunnen aanpakken. Denk aan routeplanning voor bezorgwagens, het indelen van personeelsroosters, of het samenstellen van een aandelenportefeuille. Al die problemen kun je, met wat creativiteit, in QUBO-vorm gieten.
Wat is het precies?
In een QUBO-probleem heb je een rij variabelen die elk maar twee waarden kunnen aannemen: 0 of 1. Je kunt een variabele zien als een schakelaar: aan of uit, ja of nee, wel of niet opnemen. Bij honderd beslissingen heb je dus honderd van zulke schakelaars, en elke combinatie van standen is een mogelijke 'oplossing'.
Het doel is om de combinatie te vinden die een bepaalde rekenformule zo laag mogelijk maakt, de zogeheten kostenfunctie. Die formule bestaat uit twee soorten termen: termen die afhangen van één variabele (hoe gunstig is het om deze schakelaar aan te zetten, op zichzelf), en termen die afhangen van twee variabelen samen (hoe gunstig of ongunstig is het als deze twee schakelaars tegelijk aan staan). Dat laatste heet het 'kwadratische' deel, omdat er producten van twee variabelen in voorkomen. Er zijn geen aparte regels of randvoorwaarden nodig, zoals 'maximaal drie schakelaars aan' – vandaar 'onbeperkt' (unconstrained). Dat soort regels wordt gewoon in de kostenformule verwerkt door overtredingen zwaar te 'bestraffen' met een hoge toegevoegde kostenpost.
Het aantal mogelijke combinaties groeit razendsnel: bij twintig schakelaars zijn het al meer dan een miljoen combinaties, bij honderd schakelaars meer dan er atomen in het heelal zijn. Alle combinaties één voor één uitproberen is dus al snel onbegonnen werk, ook voor de snelste computers. Dat is precies waarom QUBO interessant is: onderzoekers zoeken naar slimmere manieren, en soms naar nieuwe typen hardware, om zonder alles uit te proberen toch een goede of de beste combinatie te vinden.
Een natuurkundige true: QUBO is wiskundig vrijwel identiek aan het zogeheten Ising-model, een model dat beschrijft hoe magnetische deeltjes (spins) zich ten opzichte van elkaar instellen om een zo laag mogelijke energie te bereiken. Die gelijkenis is geen toeval: het betekent dat je een QUBO-probleem kunt 'vertalen' naar een systeem van magnetische deeltjes, en dat natuurlijke fysische processen die naar een lage energietoestand zoeken, in principe ook een QUBO-probleem kunnen 'oplossen'. Dit is de link tussen QUBO en kwantumcomputers, waar we bij 'Hoe ver is de techniek?' op terugkomen.
Wat wil men ermee bereiken?
Heel veel praktische beslissingsproblemen uit de echte wereld zijn in de kern combinatorische optimalisatieproblemen: welke route, welke indeling, welke volgorde, welke toewijzing is het beste? Veel van die problemen zijn wat wiskundigen 'NP-moeilijk' noemen, wat betekent dat er geen bekende methode is die ze voor grote aantallen variabelen snel en gegarandeerd optimaal oplost. In de praktijk moet je dus tevreden zijn met goede benaderingen in plaats van absolute zekerheid.
Het aantrekkelijke van QUBO is dat het een gemeenschappelijke taal biedt. Als je eenmaal weet hoe je jouw routeplanning, roosterprobleem of portefeuillekeuze in QUBO-vorm schrijft, kun je die ene vorm aanbieden aan heel verschillende soorten 'oplossers': klassieke software op een gewone computer, gespecialiseerde chips, of experimentele kwantumapparaten. De hoop is dat sommige van die nieuwe oplosmethoden, met name kwantum-geïnspireerde en kwantumhardware, voor bepaalde typen problemen sneller of betere oplossingen vinden dan de klassieke aanpakken van nu. Dat zou voordelen kunnen opleveren voor logistiek, energienetten, financiële planning, medicijnontwikkeling en chipontwerp, waar zelfs kleine verbeteringen in efficiëntie grote besparingen kunnen betekenen.
Voorbeelden uit de praktijk
Autobouwer Volkswagen gebruikte in 2017 een kwantumannealer van D-Wave om de route van negen bussen door de binnenstad van Lissabon te optimaliseren, met als doel opstoppingen te verminderen. Het project was vooral een proof of concept: het toonde dat je een realistisch verkeersprobleem in QUBO-vorm kon gieten en door een kwantumapparaat kon laten doorrekenen, al bleef de schaal beperkt.
De Japanse auto-onderdelenfabrikant DENSO werkte samen met D-Wave aan het optimaliseren van verkeerslichten en logistieke stromen in fabrieken, met testprojecten tussen 2017 en 2019, gericht op het verminderen van wachttijden en productieknelpunten.
Recruit Communications, onderdeel van het Japanse Recruit-concern, paste in 2018 en 2019 QUBO-gebaseerde optimalisatie toe om online advertenties en kortingscoupons beter te matchen met gebruikers, een voorbeeld van toepassing buiten logistiek.
Het Quantum Artificial Intelligence Laboratory (QuAIL) van NASA, in samenwerking met de onderzoeksorganisatie USRA, onderzocht met D-Wave-systemen hoe planningsproblemen zoals personeelsroosters en taakplanning voor ruimtemissies als QUBO geformuleerd en opgelost konden worden.
In Europa biedt het Duitse onderzoekscentrum Forschungszentrum Jülich sinds 2019 via het JUNIQ-platform toegang tot een D-Wave-kwantumannealer aan Europese onderzoeksgroepen, die er onder meer QUBO-problemen uit materiaalkunde en logistiek op testen.
Hoe ver is de techniek?
QUBO zelf is 'slechts' een wiskundige formulering en bestaat al decennia; de recente aandacht komt vooral van nieuwe hardware die claimt dit type probleem goed aan te kunnen. Het belangrijkste voorbeeld is de kwantumannealer van het Canadese bedrijf D-Wave Systems, dat sinds 2011 commerciële machines verkoopt. De nieuwste generatie, Advantage (sinds 2020), heeft meer dan vijfduizend kwantumbits (qubits) met een verbindingsstructuur genaamd Pegasus; een opvolger, Advantage2, is sinds 2023-2024 in vroege toegang beschikbaar met nog meer onderlinge verbindingen.
Toch zijn er flinke haken en ogen. Omdat de qubits op de chip niet allemaal rechtstreeks met elkaar verbonden zijn, moet een QUBO-probleem eerst worden 'ingepast' op de beperkte chipstructuur, een stap die 'minor embedding' heet. Dat kost overhead en beperkt de praktische omvang van problemen die echt op de hardware passen. Daarnaast is kwantumannealing gevoelig voor ruis en heeft het geen garantie op de optimale oplossing: het is een heuristische, gokkende methode, net als veel klassieke benaderingen.
Een belangrijke, eerlijke nuance: tot nu toe is er geen overtuigend bewijs dat kwantumannealers voor praktische QUBO-problemen sneller of beter presteren dan de beste klassieke methoden, zoals simulated annealing of tabu search op gewone of gespecialiseerde computerchips. Klassieke 'kwantum-geïnspireerde' hardware, zoals de Digital Annealer van Fujitsu (sinds 2018) en de Simulated Bifurcation Machine van Toshiba, presteert in veel benchmarks minstens zo goed en is soms makkelijker beschikbaar. In de praktijk wordt tegenwoordig vaak gebruikgemaakt van hybride oplossers, die klassieke en kwantumrekenkracht combineren, als meest werkbare tussenstap.
Wie werken eraan?
D-Wave Systems (Canada) is de pionier en marktleider in commerciële kwantumannealing-hardware specifiek gericht op QUBO-achtige problemen. Gatengebaseerde kwantumcomputerbedrijven als IBM en Google benaderen optimalisatie met een andere aanpak, via algoritmes zoals QAOA (Quantum Approximate Optimization Algorithm), maar raken hetzelfde probleemterrein.
Op het gebied van klassieke, kwantum-geïnspireerde hardware zijn Japanse technologiebedrijven sterk vertegenwoordigd: Fujitsu met de Digital Annealer, Toshiba met de Simulated Bifurcation Machine, en NEC met zogeheten vector annealing-systemen.
Op onderzoeksgebied spelen onder meer QuTech (de kwantumonderzoeksinstelling van TU Delft en TNO in Nederland), het Forschungszentrum Jülich in Duitsland, en het Amerikaanse Los Alamos National Laboratory een rol, naast universitaire samenwerkingen zoals het vroege USC-Lockheed Martin Quantum Computing Center in de Verenigde Staten. Landen die hierin fors investeren via nationale kwantumprogramma's zijn onder meer de Verenigde Staten, Japan, Duitsland, Canada en Nederland.