Exact Spin Elimination for Quadratic and k-Local Ising Optimization

Molti problemi difficili nella scienza e nell'ingegneria si riducono a trovare la singola migliore disposizione tra un numero vastissimo di possibilità. Immaginate di cercare di disporre un gruppo di persone in una stanza in modo che tutti siano il più felici possibile, date una serie complessa di regole su chi va d'accordo con chi. Nel mondo dell'informatica, questi problemi sono spesso modellati utilizzando piccoli interruttori che possono essere portati a una di due posizioni, rappresentando una scelta tra due stati. L'obiettivo è azionare gli interruttori nel modo giusto per raggiungere lo stato di energia più bassa possibile, che corrisponde alla soluzione perfetta. Tuttavia, le macchine costruite per risolvere questi problemi hanno un limite rigoroso su quanti interruttori possono contenere contemporaneamente. Quando un problema è troppo grande, o quando le regole coinvolgono gruppi di tre o più interruttori che interagiscono allo stesso tempo, la macchina semplicemente non riesce a far entrare l'intero puzzle nella sua memoria.

Per far sì che questi grandi problemi entrino negli spazi disponibili, i ricercatori hanno tradizionalmente utilizzato un trucco chiamato quadratizzazione. Questo metodo scompone le regole complesse che coinvolgono molti interruttori in regole più semplici che coinvolgono solo coppie di interruttori. Il problema è che, per fare questo, il computer deve inventare interruttori extra, immaginari, che fungano da segnaposto. Sebbene ciò semplifichi le regole, riempie la memoria limitata della macchina con queste nuove variabili, lasciando spesso poco spazio per il problema originale. È un compromesso: regole più semplici, ma meno problemi effettivi che possono essere risolti. Un nuovo studio di Natalia G. Berloff dell'Università di Cambridge propone un approccio diverso. Invece di aggiungere interruttori immaginari per semplificare le regole, lo studio suggerisce di rimuovere del tutto degli interruttori reali. Calcolando attentamente cosa accade quando un interruttore viene rimosso, i ricercatori hanno scoperto che potevano rimpicciolire la dimensione del problema senza richiedere memoria extra, permettendo alla macchina di affrontare puzzle molto più grandi rispetto a prima.

Il cuore di questo nuovo metodo è un processo chiamato eliminazione di Walsh. In una simulazione al computer standard, se si vuole rimuovere un interruttore, di solito bisogna indovinarne il valore o ignorarlo, il che rischia di perdere la risposta corretta. Questa nuova tecnica fa qualcosa di più preciso. Esamina un interruttore specifico e calcola il miglior risultato assoluto per ogni possibile disposizione dei suoi vicini. Successivamente, sostituisce le regole complesse che coinvolgono quell'interruttore con un nuovo insieme di regole che descrivono gli interruttori rimanenti, riassumendo efficacementmente l'influenza dell'interruttore rimosso senza la necessità di mantenerlo nel sistema. Fondamentalmente, il computer conserva un semplice foglio di istruzioni insieme alle nuove regole. Questo foglio dice al sistema esattamente come ricostruire la posizione dell'interruttore rimosso in seguito, garantendo che la risposta finale sia matematicamente identica a quella che sarebbe stata se l'interruttore non fosse mai stato rimosso. Il processo è esatto; non è un'approssimazione né una supposizione.

I ricercatori hanno testato questo metodo su due tipi di problemi difficili. Il primo coinvolgeva reti di interruttori in cui ciascuno interagiva con esattamente tre altri, una configurazione nota come spin glass sparsa. Il secondo coinvolgeva interazioni tra gruppi di tre interrutti alla volta. In questi test, i ricercatori hanno confrontato l'approccio standard con il loro nuovo metodo di eliminazione utilizzando un solver di annealing simulato, un tipo di algoritmo che imita il raffreddamento dei metalli per trovare stati stabili. Hanno eseguito migliaia di tentativi con un limite di tempo fisso per ogni tentativo. I risultati sono stati sorprendenti. Per i problemi di interazione a tre interruttori, il tasso di successo nel trovare la soluzione ottimale è passato da circa il 17 percento all'87,5 percento. Per i problemi più semplici a due interruttori, il tasso di successo è balzato da circa il 10 percento a quasi il 98 percento. Questo miglioramento è rimasto costante anche dopo aver tenuto conto del tempo impiegato dal computer per preparare il problema ridotto. Infatti, il tempo necessario per trovare una soluzione è diminuito di un fattore di circa 34 per i problemi più semplici e di 11 per quelli più complessi.

Per garantire che questi guadagni non fossero solo un colpo di fortuna dovuto ai casi di test specifici, i ricercatori hanno generato un nuovo set di problemi utilizzando un protocollo fisso e hanno ripetuto i test senza cambiare alcuna impostazione. Il miglioramento è persistito. In ogni singolo nuovo problema in cui la risposta corretta era nota, il modello ridotto trovava la soluzione più spesso del modello originale non ridotto. I ricercatori hanno anche confrontato il loro metodo con un'altra tecnica che tenta di fissare il valore degli interruttori basandosi su dati campionati. Quel vecchio metodo a volte compie un errore di valutazione che elimina interamente la soluzione perfetta. Al contrario, il nuovo metodo di eliminazione non ha mai commesso errori; ha preservato la possibilità della risposta migliore in ogni singolo caso, rimuovendo tra il 30 e il 40 percento degli interruttori pur mantenendo il problema risolvibile.

Oltre a rendere i macchinari esistenti più efficienti, lo studio ha dimostrato un limite teorico su quanto possa diventare grande un problema. Per una specifica classe di reti dove ogni interruttore si connette esattamente a tre altri, i ricercatori hanno dimostrato che il metodo di eliminazione può sempre rimuovere almeno un terzo degli interruttori mantenendo le regole semplici e a coppie. Ciò significa che una macchina con una capacità fissa, ad esempio 16 interruttori, potrebbe teoricamente risolvere problemi che originariamente richiedevano fino a 24 interruttori. Questa è una significativa espansione di ciò che è possibile senza costruire hardware più grande. Il metodo funziona assicurando che le nuove regole create rimuovendo un interruttore non diventino troppo complicate. I ricercatori hanno stabilito limiti rigorosi su quanti collegamenti un interruttore rimanente potesse avere, assicurando che il problema rimanesse entro le capacità degli attuali solver.

Tuttavia, lo studio ha anche identificato dove questo metodo smette di essere utile. Se le connessioni tra gli interruttori sono troppo dense, o se il problema coinvolge gruppi di quattro o più interruttori che interagiscono contemporaneamente, il processo di rimozione degli interruttori crea nuove regole troppo complesse da gestire efficientemente. In questi casi, il tempo impiegato per preparare il problema ridotto supera il tempo risparmiato dal risolvere un problema più piccolo. Il metodo brilla al massimo nei problemi "sparse" dove i collegamenti sono pochi e distanziati. I ricercatori hanno scoperto che per i problemi con interazioni a quattro vie, il tempo di preparazione era così lungo che l'approccio originale, non ridotto, era in realtà più veloce. Ciò evidenzia che il beneficio della rimozione degli interruttori dipende interamente dalla struttura del problema e dal costo delle nuove regole create.

Le implicazioni di questo lavoro vanno oltre questi specifici test. Dimostrano che il modo in cui un problema viene rappresentato a un computer è importante quanto la potenza bruta del computer stesso. Cambiando la rappresentazione per adattarla alle risorse della macchina, invece di forzare la macchina ad adattarsi alla complessità del problema, i ricercatori possono risolvere enigmi più grandi e difficili. Lo studio conferma che le riduzioni matematiche esatte possono migliorare l'ottimizzazione pratica, offrendo una via per risolvere problemi che erano precedentemente troppo grandi per l'hardware disponibile. I ricercatori hanno reso disponibile il loro software affinché altri possano utilizzarlo, permettendo alla comunità scientifica di applicare questa tecnica di eliminazione esatta alle proprie sfide. I risultati suggeriscono che, con gli strumenti matematici giusti, i limiti dell'attuale hardware di calcolo possono essere spinti oltre quanto precedentemente pensato, non costruendo macchine più grandi, ma pensando in modo più intelligente a come utilizzare quelle che abbiamo.