QAOA: kwantumhulp bij het oplossen van lastige optimalisatieproblemen
Stel je een bezorger voor die honderd pakketjes moet afleveren en de kortste route wil vinden. Het aantal mogelijke volgordes waarin dat kan, is zo astronomisch groot dat zelfs de snelste computer ter wereld ze niet allemaal kan uitproberen. Toch wil je niet zomaar een willekeurige route, maar een route die zo goed als mogelijk is. Dit soort 'kies de beste combinatie uit ontelbaar veel opties'-problemen heet een optimalisatieprobleem, en QAOA is een van de methodes die onderzoekers hebben bedacht om kwantumcomputers hierbij te laten helpen.
QAOA staat voor Quantum Approximate Optimization Algorithm, vrij vertaald: een kwantumalgoritme dat een benaderde, dat wil zeggen niet per se perfecte, oplossing zoekt voor optimalisatieproblemen. Het werd in 2014 voorgesteld door de natuurkundigen Edward Farhi, Jeffrey Goldstone en Sam Gutmann, verbonden aan het Massachusetts Institute of Technology (MIT). Belangrijk om meteen te zeggen: QAOA is geen kant-en-klare wondertechniek die vandaag al sneller rekent dan een gewone computer. Het is een veelbelovende onderzoeksrichting, waarbij een kwantumcomputer en een gewone computer voortdurend met elkaar samenwerken om, stapje voor stapje, een steeds beter antwoord te vinden.
Wat is het precies?
Om QAOA te begrijpen, helpt het eerste te snappen wat een optimalisatieprobleem in kwantumtaal betekent. Een veelgebruikt voorbeeldprobleem is MaxCut: je hebt een netwerk van punten die met lijnen verbonden zijn, en je moet de punten in twee groepen verdelen zodat zoveel mogelijk verbindingslijnen tussen de twee groepen lopen. Dit lijkt abstract, maar veel praktische vraagstukken, van netwerkontwerp tot clusterindeling, laten zich in zo'n vorm gieten.
Elke mogelijke oplossing kun je vertalen naar een reeks nullen en enen: hoort punt 1 bij groep 0 of groep 1, punt 2 bij groep 0 of 1, enzovoort. In een kwantumcomputer komt elk van die keuzes overeen met de toestand van één qubit, de kwantumversie van een bit. Vervolgens wordt er een wiskundige 'scoreregel' opgesteld, de zogeheten kostenfunctie, die aan elke combinatie een cijfer toekent: hoe hoger het cijfer, hoe beter die combinatie het optimalisatieprobleem oplost.
QAOA bouwt hierop een kwantumcircuit dat uit twee afwisselende bouwstenen bestaat. De eerste, de kostenoperatie, 'beloont' goede combinaties door hun kans op meting te vergroten. De tweede, de mixeroperatie, zorgt ervoor dat het systeem blijft zoeken en niet blijft hangen in één deeloplossing. Deze twee stappen worden om en om herhaald, in een aantal rondes dat wordt aangeduid met de letter p. Elke ronde heeft twee instelbare 'draaiknoppen' (met de namen gamma en beta), dus bij p rondes zijn er in totaal 2p knoppen om bij te stellen.
Na het uitvoeren van het circuit meet de kwantumcomputer een uitkomst, en dat wordt vele malen herhaald om een gemiddelde score te berekenen. Een gewone computer bekijkt die score en past de knoppen een beetje aan in de hoop op een hogere score, waarna de kwantumcomputer opnieuw draait. Dit heen-en-weer, bekend als een hybride kwantum-klassiek proces, gaat net zolang door tot de score niet meer verbetert. Het eindresultaat is een combinatie van nullen en enen waarvan gehoopt wordt dat die dicht bij de best mogelijke oplossing ligt.
In theorie geldt: als je p naar oneindig laat gaan, nadert QAOA een exacte methode die gegarandeerd de optimale oplossing vindt, verwant aan een techniek die adiabatische kwantumcomputatie heet. In de praktijk is dat onhaalbaar; huidige kwantumcomputers kunnen slechts een paar rondes aan voordat ruis de uitkomst verpest. Vandaar het woord 'approximate': met een klein, haalbaar aantal rondes krijg je een benadering, geen garantie.
Wat wil men ermee bereiken?
Optimalisatieproblemen zijn overal: routes plannen voor vrachtwagens, personeelsroosters maken, een aandelenportefeuille samenstellen, chips ontwerpen, of de productieplanning van een fabriek indelen. Veel van deze problemen behoren tot een categorie die wiskundigen NP-hard noemen: naarmate het probleem groter wordt, groeit de rekentijd om de exacte beste oplossing te vinden zo explosief dat geen enkele computer, kwantum of klassiek, die ooit op tijd kan garanderen.
Daarom bestaan er al langer klassieke benaderingsalgoritmes, methodes die niet de perfecte oplossing beloven maar wel snel een goede. Voor MaxCut bestaat bijvoorbeeld een klassiek algoritme (van Goemans en Williamson) dat wiskundig gegarandeerd minstens ongeveer 88 procent van de best mogelijke score haalt. De centrale vraag achter QAOA is: kan een kwantumcomputer voor bepaalde problemen een even goede of betere benadering vinden, met minder rekenstappen of op problemen die voor klassieke computers te lastig worden? Dat zou een zogeheten quantum advantage zijn, een aantoonbaar voordeel van kwantumhardware boven de beste klassieke aanpak.
Er is nog een tweede reden waarom QAOA zoveel aandacht krijgt. De kwantumcomputers van vandaag zijn nog verre van perfect: ze hebben weinig qubits en zijn gevoelig voor ruis en fouten, een categorie die onderzoekers NISQ-apparaten noemen (Noisy Intermediate-Scale Quantum). QAOA is bewust ontworpen om ook op zulke onvolmaakte machines te kunnen draaien, in plaats van te wachten op de foutgecorrigeerde kwantumcomputers van de toekomst die wellicht nog tien tot twintig jaar op zich laten wachten. Het is dus ook een test: valt er al iets nuttigs te halen uit de bescheiden kwantumhardware die nu bestaat?
Eerlijkheidshalve moet gezegd worden dat dat voordeel tot op heden niet overtuigend is aangetoond voor praktische probleemgroottes. QAOA is een veelbelovende hypothese die actief getest wordt, geen bewezen doorbraak.
Voorbeelden uit de praktijk
- Google Quantum AI (2020) voerde QAOA uit op de supergeleidende Sycamore-processor om MaxCut-achtige problemen op zogeheten niet-planaire grafen op te lossen. Het experiment liet zien dat het circuit op echte hardware draait, maar ook dat ruis al snel de kwaliteit van het antwoord beperkt naarmate het probleem groter wordt.
- IBM heeft QAOA opgenomen in zijn opensource-softwarepakket Qiskit, waarmee ontwikkelaars en onderzoekers wereldwijd het algoritme kunnen uittesten. IBM heeft daarnaast verkennend onderzoek gedaan met financiële partners, waaronder JPMorgan Chase, naar de vraag of QAOA-achtige algoritmes ooit kunnen helpen bij portefeuille-optimalisatie, het kiezen van een optimale mix van beleggingen. Dit blijft tot dusver bij onderzoekspublicaties, niet bij dagelijks gebruik in de bankensector.
- Academische en hardwarebedrijven zoals IonQ, Rigetti Computing en Quantinuum testen jaarlijks grotere MaxCut-achtige benchmarks op hun eigen kwantumchips, van gevangen ionen tot supergeleidende circuits. Dit dient vooral als maatstaf voor hoe goed de hardware vooruitgaat, meer dan als toepassing op zich.
- Volkswagen voerde in 2017 in Lissabon een spraakmakend experiment uit om verkeersstromen van taxi's te optimaliseren met kwantumhardware. Voor de duidelijkheid: dit gebruikte quantum annealing via een machine van D-Wave, een andere en oudere techniek dan QAOA, al delen beide het idee om optimalisatieproblemen in kwantumhardware te coderen.
- Gespecialiseerde start-ups zoals Zapata AI en Multiverse Computing bieden bedrijven pilotprojecten aan waarin QAOA en verwante variational-kwantumalgoritmes worden verkend voor logistiek, chemie of financiële toepassingen, doorgaans nog op kleine, experimentele schaal.
Hoe ver is de techniek?
QAOA draait vandaag daadwerkelijk op bestaande kwantumcomputers, maar alleen voor kleine speelgoedversies van problemen: enkele tientallen qubits en een klein aantal rondes (p). De belangrijkste rem is ruis: huidige kwantumchips hebben geen ingebouwde foutcorrectie, waardoor fouten zich opstapelen naarmate het circuit groter of dieper wordt.
Een tweede, meer fundamenteel obstakel is het verschijnsel van barren plateaus: bij grotere circuits kan het landschap van mogelijke scores zo vlak worden dat de klassieke optimizer geen duidelijke richting meer vindt om te verbeteren. Dit is een actief onderzoeksgebied op zich, met verschillende voorgestelde trucs om het te omzeilen, zonder dat er al een definitieve oplossing is.
Nog belangrijker: er is tot nu toe geen overtuigend bewijs dat QAOA op praktisch relevante probleemgroottes beter presteert dan de beste klassieke benaderingsalgoritmes of heuristieken zoals simulated annealing. Sterker nog, sommige theoretische analyses, onder meer van onderzoekers uit de oorspronkelijke groep rond Farhi zelf, wijzen erop dat QAOA met weinig rondes (lage p) op bepaalde problemen mogelijk nooit beter zal worden dan de bestaande klassieke aanpak. Dit debat is nog volop gaande binnen de onderzoeksgemeenschap.
Kortom: QAOA is een actief bestudeerd, experimenteel algoritme met jaarlijkse vooruitgang in het aantal qubits en de kwaliteit van de gebruikte hardware, maar het bevindt zich nog stevig in de onderzoeksfase. Er is geen aangetoond praktisch voordeel ten opzichte van klassieke computers, en niemand kan met zekerheid zeggen of, en wanneer, dat verandert.
Wie werken eraan?
De basis werd gelegd door Edward Farhi, Jeffrey Goldstone en Sam Gutmann van het MIT in 2014. Sindsdien is een breed veld van bedrijven en universiteiten actief. Onder de grote kwantumhardware- en softwarebedrijven werken onder meer IBM (met Qiskit), Google Quantum AI, IonQ, Rigetti Computing en Quantinuum aan implementaties en experimenten met QAOA. D-Wave richt zich specifiek op de verwante maar andere techniek van quantum annealing.
Daarnaast zijn er gespecialiseerde algoritme- en adviesbedrijven zoals Zapata AI en Multiverse Computing, die met industriële klanten pilotprojecten uitvoeren. Op academisch vlak blijft MIT een belangrijke speler, naast talloze universiteitsgroepen in de Verenigde Staten, Europa en Azië die theoretische en experimentele artikelen over QAOA publiceren.
Op landelijk niveau financieren onder meer het Amerikaanse National Quantum Initiative, het Quantum Flagship-programma van de Europese Unie en aanzienlijke Chinese overheidsinvesteringen breder kwantumcomputingonderzoek, waarvan optimalisatiealgoritmes zoals QAOA een klein maar zichtbaar onderdeel vormen.