Risoluzione del “Problema del Commesso Viaggiatore” tramite il Quantum Computing

Un classico problema algoritmico nel campo dell’informatica noto come Problema del Commesso Viaggiatore (TSP) è un esempio fondamentale di problema di ottimizzazione combinatoria.

Che cos’è esattamente il TSP? Questo classico della matematica consiste nel trovare il percorso più breve possibile per visitare N città esattamente una volta prima di tornare alla città di origine. Tuttavia, con l’aumento del numero di città, aumentano anche le possibili rotte e il tempo di calcolo necessario per trovare la soluzione ottimale. Mentre questo problema può essere risolto usando metodi di approssimazione, i computer quantistici potrebbero fornire soluzioni molto migliori e molto più rapidamente.

È esattamente quello che il fisico teorico il team del Prof. Dr. Jens Eisert ha dimostrato: che tali problemi possono essere risolti in modo migliore e più veloce con i computer quantistici.

Il quantum computing utilizza hardware e algoritmi che sfruttano la meccanica quantistica per risolvere problemi complessi al di là della portata dei computer convenzionali, inclusi i supercomputer. Nonostante la loro potenza, i supercomputer — enormi computer classici con migliaia di core CPU e GPU — sono limitati dalla loro dipendenza dalla tecnologia a transistor del XX secolo quando affrontano problemi di elevata complessità. 

È qui che entra in gioco la fisica quantistica. Contrariamente ai computer classici, che codificano le informazioni in bit binari (0 e 1), i computer quantistici usano bit quantistici o qubit per eseguire algoritmi quantistici multidimensionali. 

Inoltre, a differenza dei computer convenzionali, che utilizzano ventole per il raffreddamento, i computer quantistici richiedono che i loro processori quantistici siano mantenuti a temperature estremamente basse per conservare i loro stati quantistici. Ciò è ottenuto tramite superfluidi superraffreddati. 

I superconduttori sono materiali che mostrano un effetto quantistico critico, permettendo agli elettroni di muoversi al loro interno senza resistenza. Man mano che gli elettroni attraversano, si accoppiano per trasportare una carica attraverso le barriere. Quando due superconduttori sono posti su entrambi i lati di un isolante, si forma una giunzione Josephson, che viene utilizzata per realizzare qubit superconduttori.  

Un qubit è utile nel compito importante di collocare la sua informazione quantistica in uno stato di sovrapposizione, una combinazione delle possibili configurazioni del qubit. Gruppi di qubit in sovrapposizione sono in grado di creare spazi computazionali complessi e multidimensionali dove possono essere rappresentati problemi complessi.

Qui, grazie all’entanglement di due qubit, le modifiche a uno possono influenzare direttamente l’altro, mentre quando questi qubit entangled sono posti in uno stato di sovrapposizione, otteniamo un’enorme quantità di probabilità. Il calcolo su un computer quantistico funziona preparando una sovrapposizione di tutti gli stati computazionali possibili e, tramite interferenza, si trovano le soluzioni.

Naturalmente, costruire un computer quantistico con molti qubit è una procedura molto complessa, sebbene vengano esplorati diversi metodi su ciò che tali computer possono realizzare.

Secondo Eisert, che dirige un gruppo di ricerca congiunto presso Helmholtz-Zentrum Berlin (HZB), un centro di ricerca per i materiali energetici, e l’università pubblica Freie Universität Berlin:

“Ci sono molti miti al riguardo, e a volte una certa quantità di chiacchiere e hype. Tuttavia, abbiamo affrontato la questione in modo rigoroso, usando metodi matematici, e abbiamo fornito risultati solidi sull’argomento. Soprattutto, abbiamo chiarito in che senso possono esistere vantaggi.”

Il Problema Critico del Commesso Viaggiatore

Un problema di ottimizzazione, il TSP è di grande importanza economica nell’industria della logistica e della catena di approvvigionamento. Rientra nella più ampia categoria dei problemi di ottimizzazione combinatoria, che include anche la programmazione dei lavori, l’allocazione delle risorse, l’ottimizzazione di portafogli e persino il ripiegamento delle proteine, tutti critici per vari settori.

Data l’importanza sociale ed economica di questi problemi, sono stati oggetto di intensa ricerca. Pertanto, trovare la risposta a problemi come la catena di approvvigionamento più efficiente e il percorso di consegna più economico ha un impatto positivo sulla nostra vita quotidiana.

Tuttavia, ottimizzare i percorsi di consegna per più destinazioni considerando vari vincoli come la congestione del traffico, l’aumento dei costi operativi, cambiamenti improvvisi del percorso, appuntamenti d’affari dell’ultimo minuto e richieste dei clienti rende il TSP ancora più difficile da risolvere. Nonostante queste sfide, risolvere il TSP è fondamentale per la consegna efficiente delle merci, garantendo un modello di business sostenibile. 

Ci sono molti benefici nel risolvere questo problema, tra cui la riduzione della distanza e delle ore di viaggio e il risparmio di carburante. Minimizzare la distanza percorsa può contribuire a ridurre significativamente l’impronta di carbonio, il che si traduce in una migliore qualità dell’aria, un rallentamento del cambiamento climatico e crescita economica. Inoltre, risolvere il TSP può aiutare nella consegna puntuale delle merci e negli incontri tempestivi con i clienti, migliorando l’esperienza del cliente e le attività di assistenza sul campo.

Come abbiamo visto, risolvere il problema non solo aiuta le aziende, ma questi benefici si trasferiscono anche ai clienti, arricchendo l’esperienza per tutti gli interessati.

Diversi metodi possono essere usati per risolvere il problema TSP. Uno di questi è l’approccio ‘Forza Bruta’, che calcola tutte le permutazioni possibili per trovare il percorso più breve. Nel metodo branch-and-bound, il problema è suddiviso in diverse serie di sotto-problemi, con la soluzione di ogni fase che influenza quella trovata nelle fasi successive.

Nella programmazione dinamica, l’attenzione è rivolta a evitare calcoli ridondanti. Il Nearest Neighbor, invece, è un algoritmo di approssimazione in cui si inizia dalla posizione di partenza e si procede verso la più vicina. Una volta coperte tutte le città, si ritorna al punto di partenza. Sebbene pratico e relativamente veloce, questo metodo potrebbe non fornire sempre un percorso efficiente.

Con l’avanzare della tecnologia, la pianificazione e l’ottimizzazione dei percorsi possono essere eseguite in modo molto più efficace. L’Intelligenza Artificiale (AI), in particolare, può anche aiutare a risolvere il problema analizzando rapidamente una quantità enorme di dati per aiutare molte imprese moderne a prendere decisioni operative e strategiche.

I computer quantistici sono anche oggetto di studio per risolvere il problema; dopotutto offrono notevoli accelerazioni computazionali rispetto ai computer classici. È stato a lungo suggerito che questi computer possano effettivamente migliorare le approssimazioni a questi problemi.

Utilizzare le Tecniche di Quantum Computing per Risolvere il TSP

Mentre il quantum computing sta suscitando un enorme interesse e fornendo risultati promettenti per alcuni problemi, l’entità di questo vantaggio quantistico rimane in gran parte inesplorata. 

Pertanto, lo studio ha fornito una prova costruttiva completa che i computer quantistici possono effettivamente superare i computer convenzionali nel trovare approssimazioni a problemi di ottimizzazione combinatoria.

L’ultimo studio, guidato da Eisert e dal suo collega Jean-Pierre Seifert, ha utilizzato solo metodi analitici per valutare quanto un computer quantistico con qubit possa risolvere il problema del TSP. 

“Assumiamo semplicemente, indipendentemente dalla realizzazione fisica, che ci siano abbastanza qubit e osserviamo le possibilità di eseguire operazioni di calcolo con essi,” il che rivela una somiglianza a un problema comune nella crittografia, cioè la cifratura dei dati, ha spiegato Vincent Ulitzsch, dottorando presso la Technical University of Berlin. 

Successivamente, il team ha utilizzato l’algoritmo di Shor, un algoritmo quantistico, per trovare i fattori primi di un intero e risolvere una sottoclasse di questi problemi di ottimizzazione. Con ciò, il tempo di calcolo non esploderà più con l’aumento del numero di città. Aumenterà solo in modo polinomiale, cioè con Nx, dove x è una costante. In questo modo, la soluzione ottenuta è anche qualitativamente molto migliore rispetto a quella derivata dalla soluzione approssimativa usando l’algoritmo convenzionale.

Utilizzando concetti crittografici e la teoria dell’apprendimento computazionale, lo studio fornisce una “prova completamente costruttiva che i computer quantistici presentano un vantaggio superpolinomiale rispetto ai computer classici nell’approssimare problemi di ottimizzazione combinatoria.” 

Lo studio ha inoltre osservato che il team di ricerca ha fatto progressi significativi sulla importante questione di ciò che i potenziali computer quantistici possono offrire per approssimare la soluzione di problemi di ottimizzazione combinatoria, che hanno impatti sociali ed economici notevoli.

Lo studio è stato finanziato dall’Einstein Research Unit, dal Berlin Mathematics Research Center (MATH+ Cluster of Excellence), dal BMBF (Hybrid), dal BMWK (EniQmA), dal Munich Quantum Valley e dal DFG. Il Ministero Federale dell’Istruzione e della Ricerca della Germania ha inoltre fornito supporto finanziario.

Esplorare il Potenziale del Quantum Computing 

Pur essendo un grande risultato, non è stata la prima volta che il quantum computing è stato usato per risolvere il problema del commesso viaggiatore. Ci sono state numerose occasioni in cui appassionati e ricercatori hanno cercato di risolvere il problema sfruttando il quantum computing. 

Nel dicembre 2022, un paper ha proposto un algoritmo quantistico per il TSP basato sulla Grover Adaptive Search (GAS). Nell’ambito del GAS, esistono almeno due difficoltà fondamentali: le soluzioni potrebbero non essere fattibili e il numero di qubit dei computer quantistici attuali è molto limitato e non può soddisfare i requisiti minimi, limitando l’applicazione degli algoritmi quantistici ai problemi di ottimizzazione combinatoria. 

Pertanto, il paper ha perfezionato l’oracolo Hamiltonian Cycle Detection (HCD), che può rimuovere automaticamente le soluzioni impraticabili durante l’esecuzione dell’algoritmo. Hanno anche progettato una strategia di “registro di ancoraggio” per risparmiare l’uso dei qubit, considerando pienamente il requisito di reversibilità del quantum computing e superando la difficoltà che i qubit utilizzati non possano essere semplicemente sovrascritti o rilasciati. Ciò ha permesso allo studio di richiedere solo 31 qubit, e la soluzione ha avuto un tasso di successo dell’86,71%.

Nel 2019, l’appassionato di fisica auto-definito Joseph Cammidge ha scritto sull’uso di un processore quantistico di annealing, che gli ha permesso di risolvere il problema del commesso viaggiatore per sette città e ha il potenziale teorico di risolverlo per nove città una volta eliminate le limitazioni tecnologiche. 

Un nuovo metodo di calcolo, il Quantum annealing, ha mostrato il potenziale di risolvere i problemi di ottimizzazione più velocemente delle tecniche classiche. La sua teoria implica che i qubit raggiungeranno uno stato di bassa energia ottimale quando super-raffredditi. 

Tuttavia, nel 2021, uno studio finanziato da Supply Chain Digital & Data Science, Johnson & Johnson (JNJ ) ha scoperto che l’annealer quantistico può gestire solo una dimensione del problema di 8 o meno nodi, e le sue prestazioni sono inferiori sia in termini di tempo che di precisione rispetto al risolutore classico.

L’uso del quantum computing per risolvere il problema del TSP è in corso da tempo. Oltre due decenni fa, nel 2001, uno studio ha iniziato a cercare un algoritmo quantistico per risolvere il problema.

Nel documento, Buckley Hopper dell’Università dell’Alabama ha esaminato gli algoritmi quantistici di Grover e Shor. Ha osservato che l’algoritmo di Grover fornisce solo un miglioramento della radice quadrata, implicando che non può rendere un problema classico intrattabile trattabile su un computer quantistico. Per quanto riguarda l’algoritmo di Shor, Hopper ha osservato che, sebbene possa convertire un problema di fattorizzazione primo presumibilmente intrattabile in uno trattabile sulla macchina quantistica, è adatto solo a un tipo di problema molto specifico.

Nel complesso, Hopper “non ha trovato un risultato soddisfacente per un algoritmo per calcolare soluzioni approssimative al problema del commesso viaggiatore.”

Alcuni anni dopo, l’Institute of Electrical and Electronics Engineers (IEEE) ha presentato un nuovo algoritmo per risolvere il problema, ispirato sia dagli algoritmi genetici sia dal quantum computing. L’IEEE ha scoperto che i risultati dell’applicazione dell’algoritmo proposto su alcune istanze del Problema del Commesso Viaggiatore sono notevolmente migliori rispetto a quelli forniti dagli algoritmi genetici standard.

Clicca qui per saperne di più sullo stato attuale del quantum computing.

Aziende che Lavorano con il Quantum Computing 

Ora, diamo un’occhiata a un paio di nomi che stanno lavorando alla ricerca e allo sviluppo del quantum computing:

#1. IBM

International Business Machines Corporation (IBM ) è attiva in una vasta gamma di settori, tra cui AI, servizi cloud, IT, finanziamento clienti e finanziamento commerciale. Il gigante tecnologico è anche coinvolto nel quantum computing tramite la sua IBM Quantum Platform, che offre accesso pubblico e premium ai suoi servizi di quantum computing basati su cloud. Questi includono un set di processori quantistici prototipo di IBM, tutorial sul calcolo quantistico e un libro di testo interattivo.

Recentemente, gli scienziati di IBM hanno dichiarato che sono un altro passo più vicino a superare un ostacolo che sblocca il potenziale rivoluzionario dei computer quantistici. Per questo, hanno introdotto un nuovo codice di correzione degli errori quantistici, che affermano sia circa dieci volte più efficiente rispetto ai metodi precedenti. 

Alla fine dello scorso anno, l’azienda ha anche lanciato il computer quantistico chiamato Condor, con 1.121 qubit superconduttori disposti in un pattern a nido d’ape. IBM ha inoltre presentato IBM Quantum System Two, il suo primo computer quantistico modulare e architettura di supercomputing incentrata sul quantum, scalabile e quindi aggiornabile con chip che saranno lanciati nei prossimi cinque anni.

Con una capitalizzazione di mercato di 175 miliardi di dollari, le azioni di IBM sono quotate a 190,86 $, in crescita del 16,66% dall’inizio dell’anno (YTD). IBM ha registrato un fatturato (TTM) di 61,86 miliardi di dollari con un EPS (TTM) di 8,03, un P/E (TTM) di 23,76 e un ROE (TTM) del 33,36%. L’azienda paga un dividendo del 3,48%.

#2. D-Wave Systems

Questa azienda di quantum computing sviluppa e fornisce sistemi, software e servizi correlati. I suoi prodotti includono The Leap e The Advantage, e offre applicazioni quantistiche per la programmazione, la logistica, la scoperta di farmaci, i processi di produzione e altro.

All’inizio di questo mese, D-Wave ha affermato che le macchine quantistiche possono ora risolvere problemi con applicazioni reali più velocemente di qualsiasi computer ordinario. All’inizio di quest’anno, l’azienda ha annunciato un computer quantistico con 1.200 qubit, 10.000 coupler e un tempo di soluzione 20 volte più veloce su problemi di ottimizzazione difficili.

Le azioni dell’azienda sono attualmente quotate a 1,86 $, in crescita del 138,6% dall’inizio dell’anno (YTD), con una capitalizzazione di mercato di 267 milioni di dollari. Ha registrato vendite di 8,247 milioni di dollari (TTM), EPS (TTM) di -0,66 e P/E (TTM) di -3,19, e ha annunciato una crescita di oltre il 20% nelle vendite sia per il Q4 sia per i risultati di fine anno 2023, mentre le prenotazioni sono aumentate rispettivamente del 34% e dell’89%.

Curiosamente, l’amministratore delegato dell’azienda, Dr. Alan Baratz, ha dichiarato lo slancio dell’impresa, citando la partnership strategica pluriennale con Zapata AI, l’introduzione del prototipo Advantage2 da oltre 1.200 qubit, le joint venture con NEC Australia e Deloitte Canada, e la nomina dell’ex Segretario della Sicurezza Interna Kirstjen Nielsen al consiglio di amministrazione.

Conclusione

Il mercato del quantum computing dovrebbe raggiungere i 6,5 miliardi di dollari nel 2028, e il suo potenziale di risolvere il Problema del Commesso Viaggiatore (TSP) ha ripercussioni su diversi settori, come manifattura, logistica, gestione della catena di approvvigionamento, e‑commerce, trasporti e ricerca. Dopotutto, può comportare benefici sostanziali, in particolare aumentando la produttività, riducendo le spese e stimolando l’innovazione in diversi settori.

Clicca qui per l’elenco delle migliori cinque aziende di quantum computing.