In de wereld van de informatica zijn sommige problemen niet alleen moeilijk; ze zijn een specifiek soort onmogelijk voor traditionele machines om snel op te lossen. Dit zijn zogenaamde beperkte optimalisatieproblemen (constrained optimization problems). Stel je voor dat je een bezorgroute moet plannen voor een vloot vrachtwagens. Je moet elke klant precies één keer bezoeken, binnen gewichtslimieten blijven en zo snel mogelijk klaar zijn. Het aantal mogelijke routes is zo groot dat zelfs de krachtigste supercomputers langer dan het huidige tijdperk van het universum nodig zouden hebben om ze er één voor één te controleren. Decennialang hebben wetenschappers gehoopt dat quantumcomputers, die gebruikmaken van de vreemde regels van subatomaire deeltjes om informatie te verwerken, deze complexiteit zouden kunnen doorbreken. Echter, huidige quantummachines zijn luidruchtig en foutgevoelig. Ze produceren vaak antwoorden die wiskundig onmogelijk zijn, zoals een route die twee keer dezelfde stad bezoekt of een stop overslaat. De grote vraag is geweest of deze imperfecte machines nog steeds deel kunnen uitmaken van een betrouwbaar systeem dat een goede oplossing garandeert in een redelijke hoeveelheid tijd.

Een team onderzoekers heeft nu antwoord gegeven op deze vraag door een volledige pijplijn te bouwen die een luidruchtige quantumcomputer combineert met een klassieke computer om deze moeilijke problemen op te lossen. Ze richtten zich op een specifiek type quantumalgoritme genaamd de Constraint-Enhanced QAOA, die ontworpen is om de regels van het probleem te respecteren terwijl er naar het beste antwoord wordt gezocht. Hun werk laat zien dat zelfs wanneer de quantummachine fouten maakt door ruis, een slim klassiek computerprogramma die fouten direct kan herstellen. Door de quantumoutput te controleren, defecte routes te repareren en de resultaten te scoren, kan het systeem de optimale oplossing met een hoge mate van vertrouwen vinden. De onderzoekers hebben wiskundig bewezen dat deze hybride aanpak werkt in polynomiale tijd, wat betekent dat de tijd die nodig is om het probleem op te lossen op een beheersbare manier groeit naarmate het probleem groter wordt, in plaats van naar oneindig te exploderen.

De kern van hun ontdekking ligt in de manier waarop de quantum- en klassieke delen samenwerken. De quantumcomputer fungeert als een sampler, die een enorm aantal potentiële oplossingen genereert. Vanwege de ruis in de machine zijn veel van deze samples gebrekkig; ze kunnen de regels van het probleem schenden, zoals het toewijzen van twee vrachtwagens aan dezelfde weg of het onbezocht laten van een stad. In het verleden zouden wetenschappers deze slechte samples simpelweg hebben weggegooid, maar dat zou de inspanning van de quantumcomputer verspillen. In plaats daarvan hebben de onderzoekers een methode ontwikkeld waarbij de klassieke computer als een reparatiewerkplaats fungeert. Het neemt elke sample, zelfs de defecte, en gebruikt een bekende wiskundige techniek om ze te herstellen. Als een route een stad mist of duplicaten bevat, herstelt de klassieke computer het pad om het weer geldig te maken, waardoor wordt gegarandeerd dat elke stad precies één keer wordt bezocht. Dit reparatieproces is snel en deterministisch, wat betekent dat het altijd een geldig resultaat produceert.

Zodra de samples zijn hersteld, beoordeelt het systeem ze om te zien welke de beste is. De onderzoekers hebben aangetoond dat als de quantumcomputer correct is afgesteld, deze van nature een hoger aantal goede oplossingen produceert dan slechte, zelfs in een luidruchtige omgeving. Ze toonden aan dat door de quantumcircuit genoeg keren uit te voeren, het systeem gegarandeerd de perfecte oplossing zal vinden. Ze bewezen dat het aantal keren dat de machine moet draaien om het antwoord te vinden, op een voorspelbare manier groeit naarmate de probleemgrootte toeneemt. Dit betekent dat de methode niet slechts een gelukstreffer is; het is een rigoureus algoritme met prestatiegaranties. Het team noemt dit een 'fully polynomial randomized approximation scheme', een technische term die zegt dat het een betrouwbare, snelle methode is voor het vinden van bijna perfecte antwoorden op moeilijke problemen.

Om hun theorie te testen, namen de onderzoekers hun algoritme mee naar echte hardware. Ze gebruikten een 127-qubit quantumprocessor van IBM, een machine die momenteel beschikbaar is maar nog steeds aanzienlijke ruis vertoont. Ze pasten hun systeem toe op een reeks 'traveling salesman problems', waarbij het doel is om de kortste route te vinden die een specifiek aantal steden bezoekt. De problemen varieerden van kleine instanties met 16 logische variabelen tot grotere varianten met 100. Ondanks de luidruchtige omgeving werkte het systeem. De quantumcomputer genereerde een stroom ruwe data, waarvan het grootste deel ongeldig was. De klassieke reparatiestap herstelde vervolgens al deze ongeldige routes. De uiteindelijke resultaten waren indrukwekkend: voor de kleinere problemen kwam het systeem exact overeen met de beste bekende oplossingen. Voor de grotere, moeilijkere problemen vond het systeem zelfs routes die beter waren dan de eerder gepubliceerde referentie-oplossingen.

De onderzoekers verkenden ook hoe ze dit proces nog sneller konden maken. Ze realiseerden zich dat de quantumcomputer de neiging heeft om een paar zeer veelvoorkomende antwoorden en veel zeldzame antwoorden te produceren. In plaats van elke gerepareerde route te controleren, ontwikkelden ze een filteringsmethode die zich alleen richt op de meest frequente kandidaten. Deze "heavy-hitter"-aanpak verminderde de hoeveelheid werk voor de klassieke computer drastisch, waardoor de tijd die nodig is om de resultaten te verwerken werd verkort zonder de garantie te verliezen dat het beste antwoord gevonden wordt. Deze verfijning maakt de gehele pijplijn veel efficiënter, wat suggereert dat het in de toekomst zelfs naar grotere problemen kan schalen.

Een cruciaal onderdeel van hun werk was het bewijzen dat dit voordeel voortkomt uit de quantumcomputer zelf, en niet alleen uit de klassieke reparatiestap. Ze toonden aan dat als een puur klassieke computer dezelfde taak probeerde te doen — het genereren van willekeurige routes en het vervolgens repareren daarvan — het zou falen om de optimale oplossing efficiënt te vinden. Het vermogen van de quantumcomputer om zijn waarschijnlijkheid te concentreren op de beste oplossingen is wat het verschil maakt. Zonder deze quantum-bias zou de klassieke reparatiestap op zoek zijn naar een speld in een hooiberg. De studie vestigt de conclusie dat de quantummachine de essentiële voorsprong biedt, terwijl de klassieke computer zorgt voor een bruikbaar resultaat.

De bevindingen suggereren een nieuwe manier van denken over quantumcomputing. In plaats van te wachten op perfecte, foutloze machines die mogelijk nog decennia verwijderd zijn, laat dit werk zien dat we vandaag de dag krachtige instrumenten kunnen bouren door luidruchtige quantum-samplers te combineren met robuuste klassieke reparatie. Het systeem vereist niet dat de quantummachine perfect is; het hoeft alleen maar een bias te hebben naar het juiste antwoord. Door de ruis te accepteren en een systeem te bouwen dat ermee om kan gaan, hebben de onderzoekers een praktisch pad gecreëerd voor het oplossen van enkele van de moeilijkste optimalisatieproblemen in wetenschap en techniek. Hun werk op de IBM Eagle-r3 processor dient als een concrete demonstratie dat deze hybride aanpak niet alleen een theorie is, maar een functionerende realiteit die nu al bestaande benchmarks op echte problemen kan overtreffen.