Scaling Laws for Parameter Setting in Digitized Counterdiabatic QAOA

In het uitgestrekte landschap van de moderne informatica houden sommige van de meest hardnekkige uitdagingen verband met het vinden van de allerbeste arrangement tussen een duizelingwekkend aantal mogelijkheden. Of het nu gaat om het routeren van bezorgwagens door een stad, het plannen van de inzet van machines in een fabriek, of het afwikkelen van financiële transacties, dit zijn problemen van combinatorische optimalisatie. Decennialang hebben wetenschappers gekeken naar quantumcomputers—machines die gebruikmaken van de vreemde regels van de subatomaire wereld—om deze puzzels sneller op te lossen dan klassieke machines ooit zouden kunnen. Een van de meest veelbelovende instrumenten voor deze taak is een algoritme genaamd het Quantum Approximate Optimization Algorithm, of QAOA. Zie het als een geleide zoektocht: de computer bereidt een quantumtoestand voor, past een reeks operaties toe die worden gecontroleerd door specifieke getallen genaamd parameters, en meet vervolgens het resultaat om te zien hoe dicht het bij de perfecte oplossing kwam. Het nadeel is dat de computer voor elk nieuw probleem meestal een langzaam, traag proces moet doorlopen om de beste getallen te bepalen. Deze "afstemstap" vreet tijd en middelen op, wat vaak het snelheidsvoordeel dat de quantummachine zou moeten bieden, tenietdoet.

Onderzoekers Yaocheng Chen en Jiapei Zhuang hebben een manier gevonden om deze flessenhals te omzeilen voor een specifiek type quantumalgoritme dat is ontworft om gewogen problemen aan te pakken, waarbij verschillende verbindingen tussen items verschillende sterktes hebben. Ze ontdekten dat de beste instellingen voor de controles van het algoritme niet willekeurig of uniek zijn voor elk afzonderlijk probleem. In plaats daarvan volgen deze instellingen een voorspelbaar patroon gebaseerd op twee eenvoudige feiten over het probleem zelf: hoeveel verbindingen de items gemiddeld hebben, en hoe sterk die verbindingen zijn. Door duizenden verschillende probleemopstellingen in simulaties te bestuderen, heeft het team een set regels opgesteld die de optimale instellingen voor een nieuw probleem kan voorspellen door enkel naar de basisstatistieken ervan te kijken. Dit betekent dat een quantumcomputer een vers, onopgelost probleem kan krijgen en onmiddellijk de juiste instructies kan krijgen om de zoektocht te starten, zonder dat er tijd nodig is om uit te zoeken wat die instructies moeten zijn.

Het team richtte zich op een geavanceerde versie van het standaardalgoritme, bekend als digitized counterdiabatic QAOA. Terwijl de standaardversie twee soorten operaties gebruikt om door mogelijke antwoorden te schakelen, voegt deze verbeterde versie een derde soort operatie toe die ontworpen is om het systeem te voorkomen dat het vastloopt of fouten maakt terwijl het evolueert. Deze extra stap maakt het algoritme krachtiger maar ook complexer, omdat er drie sets getallen moeten worden afgestemd voor elke laag van het proces. De onderzoekers begonnen met het draaien van massale offline simulaties op een grote verscheidenheid aan graafstructuren—wiskundige kaarten van verbindingen—variërend van eenvoudige ringen tot complexe, willekeurige netwerken. Ze optimaliseerden de instellingen voor elk van deze duizenden grafen om de absolute beste prestaties te vinden.

Wat uit deze berg data naar voren kwam, was een opvallende regelmaat. Wanneer de onderzoekers corrigeerden voor de grootte van de verbindingen en het gemiddelde aantal links per item, krompen de optimale instellingen voor alle verschillende grafen samen tot een nauwe cluster. Het was alsof de specifieke details van elke graaf er minder toe deden dan de algehele schaal van het probleem. Het team realiseerde zich dat ze de beste instellingen konden beschrijven met een eenvoudige formule die de gemiddelde hoeveelheid verbindingen en de sterkte van de links als input neemt. Deze formule werkt als een universele sleutel: zodra je de basisstatistieken van een nieuw probleem kent, kun je ze invoeren en de exacte getallen krijgen die nodig zijn om de quantumcircuit te draaien. Het resultaat is een "bevroren" recept, een vaste set regels die de juiste parameters direct toewijst, waardoor het langdurige zoekproces volledig wordt overgeslagen.

Om te testen of deze kortere route daadwerkelijk werkte, draaiden de onderzoekers simulaties op 1.050 verschillende testgrafen die het algoritme nog nooit had gezien. Ze vergeleken hun formule-gebaseerde aanpak met een standaardmethode die een vaste set getallen voor iedereen gebruikt. In elk geval, van ondiepe circuits met slechts één laag operaties tot diepere circuits met vier lagen, leverde de formule-gebaseerde methode een hogere gemiddelde waarschijnlijkheid op van het bemonsteren van de optimale oplossing dan de standaard vaste aanpak. Bij een diepte van vier lagen bereikte de gemiddelde waarschijnlijkheid van de optimale oplossing voor de nieuwe methode 19,36%, vergeleken met 13,11% voor de standaard vaste aanpak. Dit voordeel bleef standhouden bij verschillende soorten netwerken en verschillende manieren van het toewijzen van verbindingssterktes. De onderzoekers testten de methode zelfs op een echte quantumprocessor, de IBM ibm_fez, met kleine, uniforme netwerken. Hoewel de ruis in de echte hardware de resultaten op diepere niveaus bemoeilijkte, vertoonde de formule-gebaseerde methode nog steeds een duidelijk voordeel op het ondiepste niveau, wat bewees dat de regels afgeleid van simulaties ook naar fysieke machines konden vertalen.

De studie onderzocht ook of deze vooraf berekende instellingen als een goed startpunt konden dienen voor verdere verfijning. In een apart experiment namen de onderzoekers de instellingen die door hun formule werden geleverd en gebruikten deze om een standaard optimalisatiezoektocht op een kleine set grafen te initialiseren. Ze ontdekten dat het starten met de getallen van de formule de zoektocht veel sneller naar een betere oplossing liet leiden dan wanneer men met een willekeurige gok zou beginnen. Sterker nog, de start met de formule-gebaseerde aanpak bereikte een hogere gemiddelde kwaliteit van de oplossing dan een willekeurige zoektocht zelfs na 500 pogingen kon bereiken. Dit suggereert dat de formule de zoektocht niet alleen vervangt, maar ook een hoogwaardig lanceerplatform biedt dat elke daaropvolgende fijnafstemming effectiever maakt.

De onderzoekers waren echter voorzichtig in het benoemen van de punten waar hun methode zou kunnen struikelen. De regels waren afgeleid van grafen met een gemiddeld aantal verbindingen, en wanneer ze de formule testten op grafen met zeer weinig verbindingen, nam de prestatie af, vooral in diepere circuits. Dit geeft aan dat hoewel de schaalwetten krachtig zijn, ze grenzen hebben en niet blindelings op elk mogelijk type netwerk toegepast mogen worden. Bovendien werd de vergelijking laag-voor-laag gemaakt, wat betekent dat het verbeterde algoritme meer fysieke operaties per stap gebruikte dan de standaardversie. De onderzoekers erkenden dat een eerlijkere vergelijking rekening zou moeten houden met het totale aantal operaties, een vraag die open blijft voor toekomstig onderzoek.

Uiteindelijk laat dit werk zien dat het gedrag van complexe quantumalgoritmen getemd kan worden door de eenvoudige geometrie van de problemen die ze oplossen te begrijpen. Door te erkennen dat de beste instellingen afhangen van de schaal van het netwerk in plaats van de specifieke details ervan, hebben de onderzoekers een moeilijk, per instantie te stemmen probleem omgezet in een eenvoudige berekening. Deze verschuiving stelt quantumcomputers in staat om hun kostbare tijd te besteden aan het oplossen van problemen in plaats van aan het leren hoe ze problemen moeten oplossen, waardoor de belofte van quantumoptimalisatie een stap dichter bij de praktische realiteit komt. De bevindingen suggereren dat voor een breed scala aan combinatorische problemen de weg naar het beste antwoord geen mysterie is dat telkens opnieuw van scratch moet worden opgelost, maar een patroon dat direct afgelezen kan worden uit de eigen structuur van het probleem.