Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization

In het opkomende veld van quantum computing proberen wetenschappers complexe puzzels op te lossen die te moeilijk zijn voor de standaardcomputers van vandaag. Een van de meest veelbelovende hulpmiddelen voor deze taak is een methode genaamd het Quantum Approximate Optimization Algorithm. Denk aan dit algoritme als een verfijnde navigator die probeert het laagste punt te vinden in een uitgestrekt, mistig landschap. Het landschap vertegenwoordigt alle mogelijke oplossingen voor een probleem, en het doel is om de absolute bodem te vinden, wat overeenkomt met het beste antwoord. De navigator kan echter niet de hele kaart in één keer zien. In plaats daarvan moet hij stappen zetten, de hoogte op elk punt meten en die informatie gebruiken om te beslissen waar hij vervolgens naartoe gaat. Dit proces steunt op een partnerschap tussen de quantummachine, die het landschap verkent, en een klassieke computer, die optreedt als de gids en de stappen aanpast op basis van wat hij leert.

De uitdaging is dat het landschap vaak vol zit met vallen, steile kliffen en verwarrende mist. In de echte wereld wordt de "mist" veroorzaakt door de imperfecte aard van de huidige quantummachines, die willekeurige fouten introduceren in de metingen. Deze ruis maakt het de klassieke gids ongelooflijk moeilijk om te weten of hij naar een betere oplossing beweegt of dat hij slechts in het duister rond dwaalt. Onderzoekers debatteren al lang over welk type gids het meest geschikt is voor deze moeilijke taak. Sommige gidsen vertrouwen op nauwkeurige, vloeiende berekeningen die goed werken wanneer de lucht helder is, terwijl anderen gebruikmaken van trial-and-error-strategieën die robuuster zijn wanneer de omgeving chaotisch is. Begrijpen welke gids het beste werkt onder welke omstandigheden is cruciaal om deze quantummachines te transformeren van experimentele curiositeiten naar praktische instrumenten.

Een team van onderzoekers zette zich af om dit debat te beslechten door tien verschillende soorten gidsen door een reeks strenge tests te sturen. Ze simuleerden een specifieke quantumopstelling met twaalf quantum bits, een diepte van drie lagen en zes instelbare instellingen, waardoor een gecontroleerde omgeving ontstond om te zien hoe elke gids presteerde. Ze testten deze gidsen op vier verschillende soorten probleemlandschappen, variërend van eenvoudige, uniforme rasters tot complexe, verstrengelde webben van interacties. Om de test realistisch te maken, voerden ze de experimenten twee keer uit: één keer met perfecte, ruisvrije metingen, en opnieuw met twee verschillende niveaus van gesimuleerde statische elektriciteit, die de fouten in echte quantumhardware vertegenwoordigen. Ze gaven elke gids een budget van maximaal dertigduizend pogingen om de beste oplossing te vinden, waarbij ze niet alleen nauwgezet bijhielden hoe goed een oplossing was die ze vonden, maar ook hoe goed ze in staat waren om de beste oplossing te identificeren vanuit de ruisige gegevens die ze ontvingen.

De resultaten onthulden een duidelijke en verrassende verschuiving in strategie, afhankelijk van de omstandigheden. Wanneer de metingen perfect waren en het landschap helder, waren de meest effectieve gidsen de gidsen die hun zoektocht meerdere keren vanaf nul konden herstarten. Deze methoden, waaronder variaties van een techniek bekend als BFH, verkenden een gebied, vonden een lokaal laag punt en sprongen vervolgens naar een volledig nieuw gebied om opnieuw te beginnen. Deze aanpak stelde hen in staat om het landschap grondig te verkennen en de diepste valleien met hoge precisie te vinden. In deze rustige omstandigheden waren de gidsen die vertrouwden op grote groepen kandidaten of complexe statistische modellen minder efficiënt, omdat ze vaak vastliepen of te traag bewogen om binnen de tijdslimiet het best mogelijke antwoord te bereiken.

Echter, op het moment dat de onderzoekers ruis introduceerden, veranderden de regels van het spel volledig. De gidsen die vertrouwden op het herstarten vanaf nul, begonnen moeite te krijgen, aangezien de willekeurige fouten het moeilijk maakten om te bepalen of een nieuw startpunt werkelijk beter was of slechts een toevalstreffer. In deze mistige omgeving namen de gidsen die een populatiegebaseerde aanpak gebruikten, specifiek een familie van methoden bekend als adaptive differential evolution, de leiding. Deze gidsen werken door een groep potentiële oplossingen te behouden die evolueren en zich aanpassen in de loop van de tijd, waarbij ze informatie delen om de onzekerheid te navigeren. De studie toonde aan dat het specifieke type adaptieve gids dat het beste presteerde, sterk afhing van het type ruis en de structuur van het probleem. Zo blonk een variant uit wanneer de ruis laag was, terwijl een andere, meer robuuste variant de duidelijke winnaar werd wanneer de ruis hoog was.

Misschien wel de meest significante bevinding was het onderscheid tussen het vinden van een goede oplossing en het succesvol selecteren ervan uit de ruis. Zelfs wanneer een gids erin slaagde om het beste punt in het landschap te bezoeken tijdens zijn zoektocht, kon de laatste stap van het beslissen welk punt als antwoord gerapporteerd moest worden, worden verpest door de statische ruis. De onderzoekers ontdekten dat de kloof tussen het beste bezochte punt en het daadwerkelijk geselecteerde punt aanzienlijk kon zijn onder hoge ruis. Ze ontdekten dat het reserveren van een klein deel van het computationele budget om de topkandidaten aan het einde opnieuw te meten, de kwaliteit van het uiteindelijke antwoord over alle methoden heen aanzienlijk verbeterde. Dit suggere houdt in dat in een wereld vol ruis, het vermogen om een veelbelovend spoor dubbel te controleren even belangrijk is als het vermogen om het te vinden.

De studie onderzocht ook of het gebruik van informatie van eenvoudigere versies van het probleem kon helpen. Sommige onderzoekers hadden een boomzoekmethode voorgesteld, waarbij oplossingen gevonden op een ondiepe diepte worden gebruikt om de zoektocht op een dieper niveau te beperken. Echter, de resultaten toonden aan dat in deze specifieke omstandigheden deze complexe boomzoekstrategie minder effectief was dan simpelweg de continue zoektocht te verfijnen met een lokale gids. De meest succesvolle aanpak bleef een combinatie van een brede, adaptieve zoektocht om de ruis te navigeren, gevolgd door een gerichte, lokale verfijning om op het antwoord in te zoomen.

Uiteindelijk toont het onderzoek aan dat er niet één enkele "beste" gids is voor quantumoptimalisatie. De keuze voor de juiste strategie hangt af van een delicaat evenwicht tussen de vorm van het probleem, het niveau van ruis in de metingen en de beschikbare middelen. Voor heldere, goed gedefinieerde problemen is een methode die regelmatig herstart superieur. Voor de rommelige, ruisige realiteit van de huidige quantumhardware zijn adaptieve populatiemethoden die kunnen leren van een groep kandidaten veel effectiever. Het werk biedt een praktische routekaart voor wetenschappers en ingenieurs, die laat zien dat om het meeste uit deze krachtige machines te halen, men de navigatietool zorgvuldig moet afstemmen op het terrein en het weer.