When is global evolutionary search useful for variational quantum algorithms? A landscape-first study

In de zoektocht naar het oplossen van problemen die te complex zijn voor de huidige supercomputers, wenden wetenschappers zich tot een nieuw soort machine: de quantumcomputer. Deze apparaten maken gebruik van de vreemde regels van de quantumfysica om tegelijkertijd vele mogelijkheden te verkennen. Het bouwen van een quantumcomputer die echte, praktische problemen kan oplossen, is echter ongelooflijk moeilijk. Een van de meest veelbelovende benaderingen omvat een hybride methode die een variationeel quantumalgoritme wordt genoemd. In deze opstelling bereidt een quantummachine een specifieke staat van materie voor, terwijl een klassieke computer optreedt als een gids, die voortdurend de instellingen van de quantummachine aanpast om de beste mogelijke oplossing te vinden. De uitdaging ligt in de taak van de gids: deze moet een uitgestrekt, ruig landschap van mogelijkheden navigeren om de laagste vallei te vinden, die de juiste oplossing vertegenwoordigt. Soms komt de gids vast te zitten in een kleine, ondiepe kuil die lijkt op de bodem maar dat niet is, waardoor de werkelijke oplossing die in een diepere vallei nabij ligt, wordt gemist.

Jarenlang hebben onderzoekers gedebatteerd over de beste manier om deze machines te begeleiden. De standaardaanpak is het gebruik van een lokale zoekopdracht, een methode die begint vanuit een willekeurig punt en naar beneden klimt langs de dichtstbijzijnde helling totdat hij een bodem bereikt. Als die bodem niet goed genoeg is, wordt het proces herhaald vanaf een nieuw willekeurig startpunt. Dit is als het sturen van vele wandelaars om het laagste punt in een bergketen te vinden; als zij allemaal vast komen te zitten in kleine holtes, kan het team de ware dalbodem missen. Een alternatief is het gebruik van een globale zoekopdracht, die het hele landschap in één keer bekijkt door een populatie van kandidaten te gebruiken die tussen verschillende gebieden kunnen springen om vastlopen te voorkomen. De grote vraag is geweest: wanneer is de dure, complexe globale zoekopdracht daadwerkelijk noodzakelijk, en wanneer is de simpelere lokale zoekopdracht voldoende? Een nieuwe studie door onderzoekers van de Technische Universiteit van Ostrava en de Universiteit van Klaipeda heeft dit beantwoord door het terrein zelf in kaart te brengen, waarbij werd onthuld dat de moeilijkheid van het probleem minder afhangt van hoe groot de bergketen is, en meer van hoe de valleien zijn gerangschikt.

De onderzoekers begonnen met het creëren van een gecontroleerde omgeving om te testen wat een landschap moeilijk maakt voor een lokale zoekopdracht. Ze gebruikten een specifiek type quantumalgoritme dat bekend staat als het Quantum Approximate Optimization Algorithm, dat is ontworpen om complexe combinatorische problemen op te lossen. In plaats van het algoritme alleen op willekeurige problemen uit te voeren, bouwden ze doelbewust twee specifieke kenmerken in de quantumcircuits in om te zien of deze kenmerken de lokale zoekopdracht zouden verwarren. Het eerste kenmerk betrof een techniek genaamd 'tied parameter reuse' (het hergebruik van gekoppelde parameters). In een standaardopstelling heeft een quantumcircuit veel lagen, en elke laag heeft zijn eigen unieke instellingen. In dit experiment dwongen de onderzoekers het circuit om exact dezelfde instellingen voor meerdere opeenvolgende lagen te gebruiken. Het tweede kenmerk hield in dat verschillende soorten interacties binnen het probleem werden gemengd, specifiek door eenvoudige twee-delige verbindingen te combineren met complexere drie-delige verbindingen. Vervolgens zetten ze een standaard lokale zoekopdracht af tegen een geavanceerdere globale zoekmethode gebaseerd op evolutionaire principes, die natuurlijke selectie nabootst door een populatie oplossingen in de loop van de tijd te laten evolueren.

De resultaten waren duidelijk en specifief. Wanneer de onderzoekers de 'tied parameter reuse' gebruikten, slaagde de lokale zoekopdracht er consequent niet in om de beste oplossingen te vinden, waarbij hij vast kwam te zitten in inferieure valleien terwijl de globale zoekopdracht slaagde. Dit gebeurde zelfs toen het totale aantal instellingen dat de computer moest aanpassen gelijk bleef. Verrassend genoeg produceerde het simpelweg dieper maken van het quantumcircuit door meer lagen met unieke instellingen niet hetzelfde probleem. De lokale zoekopdracht ging prima om met de diepere, onafhankelijke lagen. Deze bevinding weerlegt het idee dat complexiteit alleen al de vijand is; het is niet de omvang van het circuit dat problemen veroorzaakt, maar de specifieke manier waarop de instellingen worden herhaald en hergebruikt. Het tweede mechanisme, het mengen van twee-delige en drie-delige interacties, creëerde ook een landschap waarin de lokale zoekopdracht moeite had, terwijl de globale zoekopdracht de ware bodem vond. De onderzoekers ontdekten dat de moeilijkheid niet alleen voortkwam uit het hebben van veel heuvels en valleien, maar uit het hebben van valleien met zeer verschillende dieptes die van een afstand op elkaar leken, waardoor de lokale zoekopdracht genoegen nam met een ondiepe kuil in plaats van de diepe oplossing.

Om er zeker van te zijn dat deze bevindingen niet slechts een toevalstreffer waren van een enkel voorbeeld, testten de onderzoekers hun ideeën op acht volledig nieuwe, ongeziene problemen die ze nog nooit hadden gezien. Ze pasten ook dezelfde tests toe op verschillende soorten quantummodellen, inclusief die worden gebruikt voor het vinden van de beste manier om een netwerk in twee groepen te splitsen en modellen die worden gebruikt voor het simuleren van magnetische materialen. Het patroon hield stand. Op de nieuwe problemen maakten de 'tied parameter reuse' en de gemengde interacties de lokale zoekopdracht consequent ongeschikt, terwijl de globale zoekopdracht floreerde. In contrast hiermee bleven de standaardmodellen voor het simuleren van magnetische materialen gemakkelijk op te lossen voor de lokale zoekopdracht, ook al waren dit complexe quantumsystemen. Dit bevestigde dat de moeilijkheid geen inherente eigenschap is van alle quantumproblemen, maar een specifiek kenmerk van bepaalde circuitontwerpen. De studie toonde aan dat de lokale zoekopdracht faalt wanneer hij regelmatig terechtkomt in valleien die aanzienlijk slechter zijn dan de best mogelijke vallei, een situatie waar de globale zoekopdracht juist voor is ontworpen om te voorkomen.

Het meest praktische resultaat van dit werk is een nieuwe manier om te voorspellen welke zoekmethode te gebruiken is voordat de dure quantumcalculaties worden uitgevoerd. De onderzoekers ontwikkelden een eenvoudig diagnostisch hulpmiddel dat fungeert als een topografische survey. Door een paar snelle, goedkope tests op het landschap uit te voeren — door te controleren hoeveel verschillende lage punten een willekeurige zoekopdracht vindt en hoeveel die punten van elkaar verschillen in kwaliteit — konden ze met hoge nauwkeurigheid voorspellen of een globale zoekopdracht de extra inspanning waard zou zijn. In tests op vijftig nieuwe quantumdoelstellingen voorspelde dit diagnostische hulpmiddel de noodzaak voor een globale zoekopdracht in ongeveer tachtig tot tweeentachtig procent van de gevallen correct. Dit betekent dat wetenschappers in de toekomst niet meer hoeven te gokken of eindeloze benchmarks hoeven uit te voeren om een optimizer te kiezen. In plaats daarvan kunnen ze een snelle blik werpen op de vorm van het landschap van het probleem en direct beslissen of ze een enkele wandelaar of een hele expeditie moeten sturen.

De studie verduidelijkt ook wat er niet toe doet. De onderzoekers toonden expliciet aan dat het simpelweg vergroten van de diepte van het quantumcircuit of het aantal parameters niet automatisch een probleem moeilijker maakt voor een lokale zoekopdracht. De verwarring komt vaak voort uit het idee dat meer complexiteit altijd gelijk staat aan meer moeilijkheid, maar dit artikel demonstreert dat de structuur van de complexiteit degene is die telt. Als het landschap veel kleine, vergelijkbare valleien heeft, kan een lokale zoekopdracht nog steeds een goede oplossing vinden. Het is alleen wanneer het landschap een paar diepe, verborgen valleien bevat omgeven door vele ondiepe, misleidende valleien, dat de lokale zoekopdracht onbetrouwbaar wordt. Dit onderscheid is cruciaal voor het ontwerpen van betere quantumalgoritmen, en suggereert dat ingenieurs een deel van de quantumcircuitcomplexiteit kunnen inruilen voor een moeilijker klassiek optimalisatieprobleem als zij toegang hebben tot krachtige globale zoekinstrumenten.

Uiteindelijk biedt dit onderzoek een routekaart voor het navigeren door de toekomst van de quantumcomputing. Het beweegt het vakgebied weg van trial-and-error benchmarking naar een meer wetenschappelijk begrip van de problemen waar deze machines voor staan. Door de specifieke geometrische kenmerken te identificeren die lokale zoekopdrachten vangen, heeft het onderzoeksteam de gemeenschap een duidelijk signaal gegeven: wanneer een quantumprobleem een landschap heeft waar lokale zoekopdrachten regelmatig eindigen in betekenisvol inferieure bassins, is het tijd om een globale zoekopdracht in te zetten. Dit inzicht maakt een slimmere, efficiëntere benutting van quantumbronnen mogelijk, waardoor wordt gewaarborgd dat het enorme potentieel van deze machines niet verloren gaat aan de beperkingen van de instrumenten die worden gebruikt om hen te begeleiden. Het werk suggereert dat de sleutel tot het ontsluiten van het vermogen van quantumalgoritmen niet alleen ligt in het bouwen van betere machines, maar in het begrijpen van het terrein dat zij moeten doorkruisen.