Exact Spin Elimination for Quadratic and k-Local Ising Optimization

Veel moeilijke problemen in de wetenschap en techniek komen neer op het vinden van de beste enkele ordening onder een enorm aantal mogelijkheden. Stel je voor dat je probeert een groep mensen in een kamer te ordenen zodat iedereen zo gelukkig mogelijk is, gegeven een complexe set regels over wie met wie overweg kan. In de wereld van de informatica worden deze problemen vaak gemodelleerd met kleine schakelaars die naar een van de twee posities kunnen worden omgezet, wat een keuze tussen twee toestanden vertegenwoordigt. Het doel is om de schakelaars op precies de juiste manier om te zetten om de laagst mogelijke energietoestand te bereiken, wat overeenkomt met de perfecte oplossing. Echter, de machines die gebouwd zijn om deze problemen op te lossen, hebben een strikte limiet op hoeveel schakelaars ze tegelijkertijd kunnen bevatten. Wanneer een probleem te groot is, of wanneer de regels interacties tussen groepen van drie of meer schakelaars tegelijkertijd inhouden, kan de machine de hele puzzel simpelweg niet in zijn geheugen passen.

Om deze grote problemen te laten passen, gebruiken onderzoekers traditioneel een truc genaamd kwadratisering. Deze methode breekt complexe regels die veel schakelaars involveren af naar eenvoudigere regels die slechts twee schakelaars betreffen. Het nadeel is dat de computer hiervoor extra, denkbeeldige schakelaars moet verzinnen die als plaatshouders fungeren. Hoewel dit de regels vereenvoudigt, vult het het beperkte geheugen van de computer ook met deze nieuwe variabelen, waardoor er vaak geen ruimte meer overblijft voor het oorspronkelijke probleem. Het is een afruil: eenvoudigere regels, maar minder werkelijke problemen die opgelost kunnen worden. Een nieuwe studie door Natalia G. Berloff aan de Universiteit van Cambridge stelt een andere aanpak voor. In plaats van denkbeeldige schakelaars toe te voegen om de regels te vereenvoudigen, suggereert de studie om echte schakelaars volledig te verwijderen. Door zorgvuldig te berekenen wat er gebeurt wanneer een schakelaar wordt weggenomen, ontdekten de onderzoekers dat ze de omvang van het probleem konden verkleinen zonder extra geheugen nodig te hebben, waardoor de machine veel grotere puzzels dan voorheen kon aanpakken.

De kern van deze nieuwe methode is een proces genaamd Walsh-eliminatie. In een standaard computersimulatie, als je een schakelaar wilt verwijderen, moet je meestal de waarde ervan raden of hem negeren, wat het risico loopt de juiste oplossing te verliezen. Deze nieuwe techniek doet iets preciezers. Het kijkt naar een specifieke schakelaar en berekent de absoluut beste uitkomst voor elke mogelijke ordening van zijn buren. Vervolgens vervangt het de complexe regels die deze schakelaar involversen door een nieuwe set regels die de resterende schakelaars beschrijven, waardoor de invloed van de verwijderde schakelaar effectief wordt samengevat zonder deze in het systeem te hoeven houden. Cruciaal is dat de computer een eenvoudig instructieblad bijhoudt naast de nieuwe regels. Dit blad vertelt het systeem precies hoe de positie van de verwijderde schakelaar later kan worden gereconstrueerd, wat ervoor zorgt dat het uiteindelijke antwoord wiskundig identiek is aan wat het zou zijn geweest als de schakelaar nooit was verwijderd. Het proces is exact; het is niet benaderend of gokkend.

De onderzoekers testten deze methode op twee soorten moeilijke problemen. De eerste betrof netwerken van schakelaars waarbij elke schakelaar met precies drie anderen interacteerde, een opstelling die bekend staat als een ijle spin glass (sparse spin glass). De tweede betrof interacties tussen groepen van drie schakelaars tegelijkertijd. In deze tests vergeleken de onderzoekers de standaardaanpak met hun nieuwe eliminatiemethode met behulp van een simulated annealing solver, een type algoritme dat de afkoeling van metaal nabootst om stabiele toestanden te vinden. Ze voerden duizenden pogingen uit met een vaste tijdslimiet voor elke poging. De resultaten waren opmerkelijk. Voor de interactieproblemen met drie schakelaars steeg het succespercentage van ongeveer 17 procent naar 87,5 procent. Voor de eenvoudigere problemen met twee schakelaars schoot het succespercentage omhoog van ongeveer 10 procent naar bijna 98 procent. Deze verbetering hield stand, zelfs na rekening te houden met de tijd die de computer besteedde aan het voorbereiden van het gereduceerde probleem. Sterker nog, de tijd die nodig was om een oplossing te vinden, daalde met een factor van ongeveer 34 voor de eenvoudigere problemen en 11 voor de complexere problemen.

Om te garanderen dat deze winsten geen toevalstreffer waren van de specifieke testgevallen, genereerden de onderzoekers een nieuwe set problemen met een vast protocol en voerden ze de tests opnieuw uit zonder instellingen te wijzigen. De verbetering bleef bestaan. In elk nieuw probleem waar het juiste antwoord bekend was, vond het gereduceerde model de oplossing vaker dan het oorspronkelijke, niet-gereduceerde model. De onderzoekers vergeleken hun methode ook met een andere techniek die probeert de waarde van schakelaars vast te leggen op basis van gesamplede gegevens. Die oudere methode maakt soms een foutieve gok die de perfecte oplossing volledig elimineert. In contrast hiermee maakte de nieuwe eliminatiemethode nooit een foutieve gok; het behield de mogelijkheid van het beste antwoord in elk geval, waarbij het tussen de 30 en 40 procent van de schakelaars verwijderde terwijl het probleem oplosbaar bleef.

Naast het simpelweg beter maken van bestaande machines, bewees de studie een theoretische limiet voor hoe veel groter een probleem kan worden. Voor een specifieke klasse netwerken waar elke schakelaar met precies drie anderen verbonden is, bewezen de onderzoekers dat de eliminatiemethode altijd ten minste een derde van de schakelaars kan verwijderen terwijl de regels eenvoudig en tweevoudig blijven. Dit betekent dat een machine met een vaste capaciteit, bijvoorbeeld 16 schakelaars, theoretisch problemen kan oplossen die oorspronkelijk tot 24 schakelaars vereisten. Dit is een significante uitbreiding van wat mogelijk is zonder grotere hardware te bouren. De methode werkt door ervoor te zorgen dat de nieuwe regels die gecreëerd worden door het verwijderen van een schakelaar niet te complex worden. De onderzoekers stelden strikte limieten aan hoeveel verbindingen een resterende schakelaar kon hebben, om ervoor te zorgen dat het probleem binnen de mogelijkheden van huidige solvers bleef.

Echter, de studie identificeerde ook waar deze methode ophoudt nuttig te zijn. Als de verbindingen tussen schakelaars te dicht zijn, of als het probleem groepen van vier of meer schakelaars betreft die tegelijkertijd interageren, creëert het proces van het verwijderen van schakelaars nieuwe regels die te complex zijn om efficiënt te verwerken. In die gevallen weegt de tijd die besteed wordt aan het voorbereiden van het gereduceerde probleem niet op tegen de tijd die bespaard wordt door een kleiner probleem op te lossen. De methaling blinkt het meest door op ijle problemen waarbij verbindingen schaars en verspreid zijn. De onderzoekers ontdekken dat voor problemen met vierwaardige interacties de voorbereidingstijd zo lang was dat de oorspronkelijke, niet-gereduceerde aanpak feitelijk sneller was. Dit benadrukt dat het voordeel van het verwijderen van schakelaars volledig afhangt van de structuur van het probleem en de kosten van de nieuwe regels die worden gecreëerd.

De implicaties van dit werk reiken verder dan alleen deze specifieke tests. Het demonstreert dat de manier waarop een probleem aan een computer wordt gepresenteerd even belangrijk is als de ruwe kracht van de computer zelf. Door de representatie aan te passen om in de middelen van de machine te passen, in plaats van de machine te dwingen zich aan te passen aan de complexiteit van het probleem, kunnen onderzoekers grotere en moeilijkere puzzels oplossen. De studie bevestigt dat exacte wiskundige reducties praktische optimalisatie kunnen verbeteren, wat een pad biedt naar het oplossen van problemen die voorheen te groot waren voor de beschikbare hardware. De onderzoekers hebben hun software beschikbaar gesteld voor anderen om te gebruiken, zodat de wetenschappelijke gemeenschap deze exacte eliminatietechniek op hun eigen uitdagingen kan toepassen. De resultaten suggereren dat met de juiste wiskundige instrumenten de grenzen van de huidige computerhardware verder kunnen worden gedrukt dan voorheen gedacht, niet door grotere machines te bouwen, maar door slimmer na te denken over hoe we de machines die we al hebben kunnen gebruiken.