Un noto problema di calcolo cerca di trovare il percorso più efficiente per un venditore ambulante per visitare i clienti in un certo numero di città. Apparentemente semplice, in realtà è sorprendentemente complesso e molto studiato, con implicazioni in campi di vasta portata come la produzione e il controllo del traffico aereo.

I ricercatori della University of Central Florida e della Boston University hanno sviluppato un nuovo approccio per risolvere più rapidamente problemi di calcolo così difficili. Come riportato il 12 maggio in Comunicazioni sulla natura , hanno scoperto un modo di applicare la meccanica statistica, una branca della fisica, per creare algoritmi più efficienti che possono essere eseguiti su computer tradizionali o su un nuovo tipo di macchina computazionale quantistica, ha detto il professor Eduardo Mucciolo, presidente del Dipartimento di Fisica del College of Sciences dell'UCF.

La meccanica statistica è stata sviluppata per studiare i solidi, gas e liquidi su scala macroscopica, ma ora è usato per descrivere una varietà di stati complessi della materia, dal magnetismo alla superconduttività. Sono stati applicati anche metodi derivati ​​dalla meccanica statistica per comprendere i modelli di traffico, il comportamento delle reti di neuroni, valanghe di sabbia e fluttuazioni del mercato azionario.

Esistono già algoritmi di successo basati sulla meccanica statistica che vengono utilizzati per risolvere problemi computazionali. Tali algoritmi mappano i problemi su un modello di variabili binarie sui nodi di un grafo, e la soluzione è codificata sulla configurazione del modello con l'energia più bassa. Costruendo il modello nell'hardware o in una simulazione al computer, i ricercatori possono raffreddare il sistema finché non raggiunge la sua energia più bassa, rivelando la soluzione.

"Il problema con questo approccio è che spesso è necessario superare transizioni di fase simili a quelle che si trovano quando si passa da una fase liquida a una vetrosa, dove esistono molte configurazioni concorrenti a bassa energia, " ha detto Mucciolo. "Tali transizioni di fase rallentano il processo di raffreddamento a passo d'uomo, rendendo il metodo inutile."

Mucciolo e i colleghi fisici Claudio Chamon e Andrei Ruckenstein della BU hanno superato questo ostacolo mappando il problema computazionale originale su un elegante modello statistico senza transizioni di fase, che chiamarono modello dei vertici. Il modello è definito su un reticolo bidimensionale e ogni vertice corrisponde a una porta logica reversibile collegata a quattro vicini. I dati di input e output si trovano ai confini del reticolo. L'uso di porte logiche reversibili e la regolarità del reticolo sono stati ingredienti cruciali per evitare l'intoppo della transizione di fase, ha detto Mucciolo.

"Il nostro metodo fondamentalmente esegue le cose al contrario in modo da poter risolvere questi problemi molto difficili, Disse Mucciolo. “A ciascuna di queste porte logiche assegniamo un'energia. Lo abbiamo configurato in modo tale che ogni volta che queste porte logiche sono soddisfatte, l'energia è molto bassa - quindi, quando tutto è soddisfatto, l'energia complessiva del sistema dovrebbe essere molto bassa."

Chamon, un professore di fisica alla BU e il capo squadra, ha affermato che la ricerca rappresenta un nuovo modo di pensare al problema.

"Questo modello non mostra una transizione di fase termodinamica di massa, è stato così eliminato uno degli ostacoli al raggiungimento delle soluzioni presenti nei modelli precedenti, " Egli ha detto.

Il modello del vertice può aiutare a risolvere problemi complessi nell'apprendimento automatico, ottimizzazione del circuito, e altre importanti sfide computazionali. I ricercatori stanno anche valutando se il modello può essere applicato alla scomposizione in fattori di semi-primi, numeri che sono il prodotto di due numeri primi. La difficoltà di eseguire questa operazione con semiprimi molto grandi è alla base della crittografia moderna e ha offerto una logica chiave per la creazione di computer quantistici su larga scala.

Inoltre, il modello può essere generalizzato per aggiungere un altro percorso verso la soluzione di complessi problemi computazionali classici sfruttando il parallelismo della meccanica quantistica, il fatto che, secondo la meccanica quantistica, un sistema può trovarsi in molti stati classici contemporaneamente.

"Il nostro documento presenta anche un quadro naturale per la programmazione di dispositivi computazionali speciali, come le macchine D-Wave Systems, che utilizzano la meccanica quantistica per accelerare i tempi di soluzione dei problemi computazionali classici, " disse Ruckenstein.

Zhi Cheng Yang, uno studente laureato in fisica alla BU, è anche coautore del documento. Le università hanno richiesto un brevetto su aspetti del modello di vertice.