Quantum circuit evolutionary framework applied on set partitioning problem

Dit artikel stelt een evolutionair raamwerk voor kwantumkringen voor dat gebruikmaakt van variabele topologie en een pseudo-counterdiabatische evolutionaire term om partitieproblemen effectief op te lossen door convergentiestagnatie te overwinnen en de noodzaak van klassieke optimalisatoren te elimineren.

De kern

Stel je voor dat je probeert een enorm, complex puzzel op te lossen. Het doel is om een groep mensen (zoals luchtvaartbemanningen) in teams te verdelen zodat elke vlucht precies één keer wordt gedekt, zonder overlappingen of gemiste diensten, terwijl de kosten zo laag mogelijk worden gehouden. In de wereld van de wiskunde heet dit het Set Partitioning Problem (Probleem van de Partitie van Mengen). Het is een berucht moeilijke uitdaging die exponentieel moeilijker wordt naarmate je meer mensen en vluchten toevoegt.

Dit artikel introduceert een nieuwe manier voor quantumcomputers om deze puzzel aan te pakken. In plaats van het standaard "recept" te gebruiken dat de meeste quantumalgoritmen volgen, hebben de auteurs een raamwerk ontwikkeld dat de computer in staat stelt om zijn eigen recept te laten evolueren terwijl het werkt.

Hier is een uiteenzetting van hun aanpak met behulp van eenvoudige analogieën:

1. De Oude Weg: Het "Vaste Blauwdruk" (VQE)

De meeste huidige quantumalgoritmen, zoals de Variational Quantum Eigensolver (VQE), werken als een chef-kok die een strikt, onveranderlijk receptenboek volgt.

• De Opzet: De structuur van de "schakeling" (de stappen die de computer neemt) is vast. Je kunt geen ingrediënten toevoegen of verwijderen; je kunt alleen de hoeveelheden aanpassen (de parameters).
• Het Probleem: Naarmate de puzzel groter wordt, komt de chef-kok vaak vast te zitten in een "vlakke vallei". Stel je voor dat je door een mistig veld loopt waar de grond perfect vlak is. Hoe je ook stapt, je gaat niet omhoog of omlaag. Je kunt niet zeggen of je dichter bij de oplossing komt of niet. In de quantumfysica heet dit een Barren Plateau (Dode Vlakte). De computer stopt met leren omdat het geen richting kan vinden om te verbeteren.

2. De Nieuwe Weg: De "Evoluerende Beeldhouwer" (QCE)

De auteurs stellen een raamwerk voor genaamd Quantum Circuit Evolution (QCE). In plaats van een vast recept, stel je een beeldhouwer voor die begint met een klein klontje klei en op elke stap mag klei toevoegen, verwijderen of herschikken.

• Hoe het werkt: De computer begint met een zeer eenvoudige schakeling (misschien slechts één poort). Het creëert vervolgens een "familie" van lichtjes verschillende versies van zichzelf door willekeurig de structuur te muteren (een nieuwe stap toevoegen, een oude verwijderen, of een verbinding veranderen).
• De Selectie: Het test al deze versies. De versie die de puzzel het beste oplost, overleeft om de "ouder" te zijn voor de volgende ronde. De anderen worden weggegooid.
• Het Voordeel: Omdat de structuur zelf verandert, zit de computer niet vast in een vlakke vallei. Het kan zijn hele aanpak herschikken om een weg uit de mist te vinden.

3. De Twee Geteste Strategieën

Het artikel testte twee specifieke varianten van deze "Evoluerende Beeldhouwer"-aanpak:

• Strategie A: De Pure Evolusionist (Ansatz-Free)
  Deze versie begint met bijna niets en laat de computer de structuur volledig via trial and error uitzoeken, net als natuurlijke selectie. Het raadt niet hoe de oplossing eruit moet zien; het evolueert gewoon tot het werkt.

• Strategie B: De Fysica-Geïnspireerde Evolusionist (Pseudo-Counterdiabatic)
  Dit is de "ster" van het artikel. De auteurs gaven de computer een hint gebaseerd op de fysica van het probleem. Ze voegden een speciale "duwtje" (een pseudo-counterdiabatic term) toe aan de schakeling.

  • De Analogie: Stel je voor dat je een zware doos een heuvel op duwt. De "Pure Evolusionist" duwt gewoon willekeurig tot het een weg omhoog vindt. De "Fysica-Geïnspireerde" versie kent de vorm van de heuvel en voegt een specifieke tegenkracht toe om de doos soepel te houden, zodat deze niet vast komt te zitten in de vlakke plekken.
  • Het Resultaat: Deze strategie presteerde het beste. Het vermijdt het "vastzitten" (convergentiestagnatie) veel beter dan de andere methoden, zelfs wanneer de puzzel zeer groot was.

4. De Resultaten

De auteurs testten deze methoden op een simulator (een computerprogramma dat als een quantumcomputer werkt) met 35 verschillende versies van het luchtvaartplanningspuzzel.

• De Winnaar: De Fysica-Geïnspireerde Evolutie-methode (APCD-QCE) vond consequent betere oplossingen dan de standaard "Vaste Blauwdruk"-methode (VQE).
• Het Pijnpunt: Hoewel de nieuwe methoden veel beter waren, hadden ze nog steeds moeite wanneer de puzzel extreem groot werd (rond de 20 qubits). Zelfs de evoluerende beeldhouwer had soms niet genoeg tijd of complexiteit om de perfecte oplossing te vinden.
• Ruis: Ze testten ook wat er gebeurt wanneer de computer fouten maakt (het simuleren van echte "ruis"). De nieuwe methoden hielden zich redelijk goed, hoewel de prestaties daalden, wat te verwachten is.

De Conclusie

Het artikel beweert dat door een quantumcircuit zijn eigen vorm te laten veranderen in plaats van alleen zijn instellingen aan te passen, we de "dode hoeken" kunnen vermijden die huidige algoritmen opsluiten. Specifiek helpt het toevoegen van een op fysica gebaseerd "duwtje" aan dit evoluerende proces de computer om sneller betere oplossingen te vinden.

Hoewel dit nog niet elk probleem oplost (vooral niet de allergrootste), biedt het een veelbelovend nieuw pad voor het gebruik van quantumcomputers om complexe optimalisatieproblemen op te lossen zoals planning en resourcebeheer, waarbij mogelijk de noodzaak wordt omzeild dat klassieke computers het zware werk van optimalisatie moeten doen.

Technische samenvatting

Technische Samenvatting: Evolutionair Kwantumkringskader Toegepast op het Probleem van de Partitie van een Menge

Probleemdefinitie
Het artikel behandelt het Probleem van de Partitie van een Menge (SPP), een bekende NP-moeilijke combinatorische optimalisatie-uitdaging. Het SPP houdt in het verdelen van een verzameling elementen in onderling uitsluitende en exhaustieve deelverzamelingen om het totale gewicht te minimaliseren, terwijl ervoor wordt gezorgd dat elk element precies aan één deelverzameling behoort. Praktische toepassingen omvatten de planning van bemanningen bij luchtvaartmaatschappijen. Om dit op kwantumhardware op te lossen, formuleren de auteurs het SPP als een Quadratische Ongedwongen Binaire Optimalisatie (QUBO)-probleem, dat vervolgens wordt gemapt naar een Ising-Hamiltoniaan. De studie richt zich specifiek op de beperkingen van huidige Variatie Kwantumalgoritmen (VQA's), zoals de Variatie Kwantum-eigensolver (VQE), die vaak lijden aan "vruchtbare plateaus" — een fenomeen waarbij gradiënten exponentieel verdwijnen naarmate het aantal qubits toeneemt, wat leidt tot stagnatie in de convergentie.

Methodologie
De auteurs stellen een Evolutionair Kwantumkringskader (QCE) voor dat afwijkt van de standaard VQE-benadering. In tegenstelling tot VQE, dat een vaste krings-topologie (ansatz) gebruikt met variërende parameters die worden geoptimaliseerd door een klassieke optimizer, evolueert het QCE-kader de krings-topologie zelf. De studie evalueert twee verschillende strategieën binnen dit kader:

1. Ansatz-vrije Evolutionaire Kwantumkring (AF-QCE):

   • Geïnspireerd door eerdere literatuur [13], begint deze aanpak met een minimale kring (een enkele willekeurige poort) en evolueert iteratief zonder een vooraf gedefinieerde ansatz.
   • De evolutie vertrouwt op mutatie-operaties: INSERT (een poort toevoegen), DELETE (een poort verwijderen), SWAP (een poort vervangen) en MODIFY (poortparameters aanpassen).
   • Er wordt een populatie van kringen gegenereerd, gemeten en de best presterende kring wordt geselecteerd als ouder voor de volgende generatie, waardoor een monotoon afname van de kostenfunctie wordt gewaarborgd.

2. Ansatz met Pseudo-Counterdiabatische Evolutionaire Term (APCD-QCE):

   • Deze aanpak integreert door de fysica geïnspireerde structuur in de ansatz om de convergentie te verbeteren. Het maakt gebruik van een Hamiltoniaan $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$, waarbij $H_{ad}$ een Hamiltoniaan voor adiabatische tijds-evolutie voorstelt en $H_{pcd}$ een pseudo-counterdiabatische evolutionaire term is.
   • De unitaire operator wordt gedefinieerd als $U = U_{ad}U_{pcd}$. Het $U_{ad}$-component is vast (één Trotter-stap), terwijl $U_{pcd}$ wordt geëvolueerd met dezelfde evolutionaire mutatiestrategie als AF-QCE.
   • De voorbereiding van de initiële toestand maakt gebruik van $|+\rangle^{\otimes n}$, en specifieke parameterinstellingen ($\beta=0, \delta=0.5$) worden toegepast om de verkenning van de Hilbertruimte te faciliteren.

Experimentele Opstelling
Experimenten werden uitgevoerd met de Qiskit-bibliotheek op een high-performance simulator (KUATOMU) onder twee scenario's:

• Ruisvrij: 35 instanties van het SPP (variërend van 6 tot 20 qubits) werden getest.
• Ruisbeïnvloed: Simulaties omvatten depolariserende foutkanalen ($\epsilon = 0.01$) op specifieke qubits om beperkingen van NISQ-apparaten na te bootsen.
• Vergelijking: De QCE-strategieën werden gebenchmarkt tegen de standaard VQE (met behulp van een tweelokaal lineair verstrengelingsansatz en de COBYLA-optimizer).
• Maatstaf: Prestaties werden gemeten met de Benaderingsratio ($R$), gedefinieerd als de verhouding tussen een klassieke referentiewaarde (Gurobi-oplosser) en de minimale verwachtingswaarde gevonden door het kwantumalgoritme.

Belangrijkste Resultaten

• Superioriteit ten opzichte van VQE: In ruisvrije scenario's presteerden zowel AF-QCE als APCD-QCE significant beter dan VQE. De VQE-prestaties degradeerden snel naarmate het aantal qubits toenam (vaak falend in convergentie voor instanties $\ge 10$ qubits), terwijl de evolutionaire benaderingen betere prestaties behielden.
• APCD-QCE Prestaties: De APCD-QCE-strategie toonde de meest robuuste resultaten, met het behalen van een benaderingsratio van 1,00 (optimaal) in 25 van de 35 instanties. Het vermijdde effectief convergentiestagnatie in de meeste gevallen waarin VQE en AF-QCE worstelden.
• Schaalbaarheidsbeperkingen: Ondanks de verbeteringen bleven schaalbaarheidsuitdagingen bestaan. Voor 20-qubit instanties (specifiek 20.1, 20.6 en 20.7) vertoonden alle methoden, inclusief APCD-QCE, tekenen van convergentiestagnatie, met een aanzienlijke daling van de benaderingsratio's.
• Invloed van Ruis: In ruisbeïnvloede simulaties degradeerden de prestaties voor alle algoritmen, met name bij kleinere instanties. De QCE-kaders behielden echter over het algemeen vergelijkbare of betere prestaties ten opzichte van VQE.

Betekenis en Claims
Het artikel beweert dat het voorgestelde QCE-kader een veelbelovend alternatief biedt voor variatiealgoritmen met vaste ansatz voor integer-optimalisatieproblemen. Belangrijke bijdragen zijn:

• Mitigatie van Stagnatie: Het kader, met name de APCD-QCE-variant, toont een opmerkelijk vermogen om de convergentiestagnatie te vermijden die geassocieerd is met vruchtbare plateaus in standaard VQA's.
• Eliminatie van Klassieke Optimizers: Door de krings-topologie direct te evolueren, omzeilt de procedure de noodzaak van klassieke optimizers (zoals COBYLA) om parameters af te stemmen, wat een knelpunt in huidige VQA-werkstromen aanpakt.
• Pad naar Schaalbaarheid: Hoewel het geen volledige oplossing is voor de stagnatie bij 20 qubits, suggereren de resultaten dat kringen met variabele topologie een "interessant pad" bieden voor het oplossen van optimalisatieproblemen op grotere schaal. De auteurs merken op dat de APCD-QCE-strategie "bijna immuun" is voor convergentiestagnatie-effecten gegeven een voldoende groot aantal generaties, hoewel het ontsnappen aan lokale minima in het mutatielandschap een uitdaging blijft.

De auteurs concluderen dat, hoewel de methode schaalbaarheidsproblemen ondervindt bij toenemend aantal qubits, de integratie van door de fysica geïnspireerde termen (pseudo-counterdiabatisch) in evolutionair kringszoektocht bemoedigende resultaten oplevert voor het oplossen van combinatorische problemen op NISQ-apparaten.