Risolvere il "problema del commesso viaggiatore" attraverso l'informatica quantistica

Un classico problema algoritmico nel campo dell'informatica noto come problema del commesso viaggiatore (TSP) è un ottimo esempio di problema di ottimizzazione combinatoria.

Cos'è esattamente il TSP? Questo classico della matematica consiste nel trovare il percorso più breve possibile per visitare un numero N di città esattamente una volta prima di tornare alla città di origine. Tuttavia, all’aumentare del numero delle città, aumentano anche i percorsi possibili e il tempo di calcolo necessario per trovare la soluzione ottimale. Sebbene questo problema possa essere risolto utilizzando metodi di approssimazione, i computer quantistici potrebbero fornire soluzioni molto migliori e molto più rapidamente. 

Questo è esattamente ciò che il fisico teorico Il team del Prof. Dr. Jens Eisert ha dimostrato: che tali problemi possono essere risolti meglio e più velocemente con i computer quantistici.

L’informatica quantistica utilizza hardware e algoritmi che sfruttano la meccanica quantistica per risolvere problemi complessi oltre la portata dei convenzionali, compresi 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 transistor del 20° secolo quando risolvono problemi con un alto grado di complessità. 

È qui che entra in gioco la fisica quantistica. A differenza dei computer classici, che codificano le informazioni in bit binari (0 e 1), i computer quantistici utilizzano 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 fredde per mantenere i loro stati quantistici. Ciò si ottiene attraverso superfluidi superraffreddati. 

I superconduttori sono materiali che presentano un effetto quantomeccanico critico, consentendo agli elettroni di muoversi attraverso di essi senza resistenza. Quando gli elettroni lo attraversano, si accoppiano per trasportare una carica attraverso le barriere. Quando due superconduttori vengono posizionati su entrambi i lati di un isolante, si forma una giunzione Josephson, che viene utilizzata per condurre qubit superconduttori.  

Un qubit è utile nell'importante compito 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 in cui è possibile rappresentare problemi complessi.

Qui, mediante l'entanglement di due qubit, le modifiche apportate a uno possono avere un impatto diretto sull'altro, mentre quando questi qubit entangled vengono posti in uno stato di sovrapposizione, otteniamo così tante probabilità. Il calcolo su un computer quantistico funziona preparando una sovrapposizione di tutti i possibili stati computazionali e, attraverso l'interferenza, si trovano le soluzioni.

Naturalmente, costruire un computer quantistico con molti qubit è una procedura molto complessa, anche se si stanno esplorando diversi metodi per capire cosa possono realizzare tali computer. 

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

“Ci sono molti miti a riguardo, e talvolta una certa quantità di aria fritta e pubblicità. Tuttavia, abbiamo affrontato la questione in modo rigoroso, utilizzando metodi matematici, e abbiamo fornito risultati concreti sull’argomento. Soprattutto abbiamo chiarito in che senso possono esserci dei vantaggi”. 

Il problema critico del venditore ambulante

Essendo un problema di ottimizzazione, il TSP è di grande importanza economica nel settore della logistica e della catena di fornitura. Rientra nella categoria più ampia dei problemi di ottimizzazione combinatoria, che comprende anche la pianificazione dei lavori, l'allocazione delle risorse, l'ottimizzazione del portafoglio e persino il ripiegamento delle proteine, tutti fondamentali per vari settori.

Considerata la portata sociale ed economica di questi problemi, essi sono stati oggetto di intense ricerche. Pertanto, trovare la risposta a problemi quali 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, improvvisi cambiamenti di percorso, appuntamenti di lavoro dell'ultimo minuto e richieste dei clienti rende TSP ancora più difficile da risolvere. Nonostante queste sfide, la risoluzione del TSP è fondamentale per la consegna efficiente delle merci, che garantisce un modello di business fattibile. 

I vantaggi derivanti dalla risoluzione di questo problema sono numerosi, tra cui la riduzione della distanza e delle ore di viaggio e il risparmio sul consumo di carburante. Ridurre al minimo la distanza percorsa può contribuire a ridurre significativamente l’impronta di carbonio, il che si traduce in una migliore qualità dell’aria, in un rallentamento del cambiamento climatico e in una crescita economica. Inoltre, la risoluzione del TSP può aiutare a garantire la consegna puntuale delle merci e incontri tempestivi con i clienti, il che migliora l'esperienza del cliente e le attività di assistenza sul campo.

Come abbiamo visto, risolvere il problema non solo aiuta le aziende, ma questi vantaggi si riversano anche sui clienti, arricchendo l’esperienza di tutti i soggetti coinvolti.

Esistono diversi metodi per risolvere il problema TSP. Uno di questi è l'approccio "Brute-Force", che calcola tutte le possibili permutazioni per trovare il percorso più breve. Nel metodo branch-and-bound, il problema viene scomposto in diverse serie di sottoproblemi, in cui la soluzione di ogni fase influenza la soluzione trovata nelle fasi successive.

Nella programmazione dinamica, l'obiettivo è evitare calcoli ridondanti. Il vicino più vicino, invece, è un algoritmo di approssimazione in cui si inizia con la posizione di partenza e poi ci si ferma a quella più vicina. Una volta coperte tutte le città, tornerai al punto di partenza. Sebbene pratico e relativamente rapido, 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 un’enorme quantità di dati per aiutare molte imprese moderne a prendere decisioni operative e strategiche.

Per risolvere il problema si stanno studiando anche i computer quantistici; dopo tutto, offrono notevoli accelerazioni computazionali rispetto ai computer classici. È stato a lungo suggerito che questi computer potrebbero effettivamente aiutare a migliorare l'approssimazione di questi problemi. 

Utilizzo di tecniche di calcolo quantistico per risolvere TSP

Sebbene l’informatica quantistica stia riscuotendo un enorme interesse e fornendo risultati promettenti per alcuni problemi, la portata di questo vantaggio quantistico rimane in gran parte inesplorata. 

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

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

"Indipendentemente dalla realizzazione fisica, assumiamo semplicemente che ci siano abbastanza qubit e analizziamo le possibilità di eseguire operazioni di calcolo con essi", il che rivela una somiglianza con un problema comune nella crittografia, cioè la crittografia dei dati, ha spiegato Vincent Ulitzsch , un dottorato di ricerca. studente presso l'Università Tecnica di Berlino. 

Il team ha quindi 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. In questo modo, il tempo di calcolo non aumenterà più vertiginosamente con l'aumentare del numero di città. Aumenterà solo in modo polinomiale, ovvero con Nx, dove x è una costante. In questo modo, la soluzione ottenuta è anche qualitativamente molto migliore di quella derivata dalla soluzione approssimata utilizzando l'algoritmo convenzionale.

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

Lo studio ha inoltre rilevato che il gruppo di ricerca ha compiuto progressi significativi sull’importante questione di quali potenzialità i computer quantistici possono offrire per approssimare la soluzione dei problemi di ottimizzazione combinatoria, che hanno sostanziali impatti sociali ed economici.

Lo studio è stato finanziato dall’Einstein Research Unit, dal Berlin Mathematics Research Center (MATH+ Cluster of Excellence), dal BMBF (Hybrid), dal BMWK (EniQmA), dalla Monaco Quantum Valley e dal DFG. Anche il Ministero federale dell’Istruzione e della Ricerca tedesco ha fornito sostegno finanziario.

Esplorare il potenziale del calcolo quantistico 

Pur essendo un grande risultato, non è la prima volta che l'informatica quantistica viene utilizzata per risolvere il problema del commesso viaggiatore. Sono molti gli esempi di appassionati e ricercatori che hanno cercato di risolvere il problema utilizzando l'informatica quantistica. 

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

Pertanto, il documento ha perfezionato l’oracolo Hamiltonian Cycle Detection (HCD), che può rimuovere automaticamente le soluzioni poco pratiche durante l’esecuzione dell’algoritmo. Hanno inoltre progettato una strategia di “registro di ancoraggio” per risparmiare l’utilizzo dei qubit, considerando pienamente il requisito di reversibilità del calcolo quantistico e superando la difficoltà che i qubit utilizzati non vengano semplicemente sovrascritti o rilasciati. Ciò ha consentito allo studio di richiedere solo 31 qubit e la soluzione ha avuto un tasso di successo dell'86.71%.

Nel 2019, l'autodefinito intenditore di fisica Joseph Cammidge ha scritto sull'utilizzo di un processore quantistico di ricottura, 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, la ricottura quantistica, ha mostrato il potenziale per risolvere problemi di ottimizzazione più velocemente rispetto alle tecniche classiche. La sua teoria implica che i qubit raggiungeranno uno stato ottimale di bassa energia quando saranno superraffreddati. 

Tuttavia, nel 2021, a studio finanziato da Supply Chain Digital & Data Science, Johnson & Johnson ha scoperto che il ricottore quantistico può gestire solo problemi di dimensioni pari o inferiori a 8 nodi e le sue prestazioni sono inferiori sia in termini di tempo che di precisione rispetto al solutore classico.

L’uso dell’informatica quantistica per risolvere il problema del TSP è in corso ormai da un po’. Oltre due decenni fa, nel 2001, è iniziato uno studio ricerca per un algoritmo quantistico per risolvere il problema.

Nell'articolo, Buckley Hopper dell'Università dell'Alabama ha esaminato gli algoritmi di Grover e Shor per computer quantistici. Ha osservato che l'algoritmo di Grover fornisce solo un miglioramento di radice quadrata, il che implica che non può rendere trattabile su un computer quantistico un problema classicamente intrattabile. Per quanto riguarda l'algoritmo di Shor, Hopper ha osservato che, sebbene possa convertire un problema di fattori primi presumibilmente intrattabile in uno trattabile sulla macchina quantistica, è adatto solo per un tipo di problema molto specifico. 

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

Alcuni anni dopo, l’Institute of Electrical and Electronics Engineers (IEEE) presentata un nuovo algoritmo per risolvere il problema, ispirato sia agli algoritmi genetici che all’informatica quantistica. L'IEEE ha scoperto che i risultati dell'applicazione dell'algoritmo proposto su alcuni casi del problema del commesso viaggiatore sono considerevolmente migliori di quelli forniti dagli algoritmi genetici standard.

Clicca qui per conoscere lo stato attuale dell’informatica quantistica.

Aziende che lavorano con l'informatica quantistica 

Ora diamo un'occhiata ad alcuni nomi che stanno lavorando alla ricerca e allo sviluppo del computer quantistico:

#1. IBM

International Business Machines Corporation è attiva in un'ampia gamma di settori, tra cui intelligenza artificiale, servizi cloud, IT, finanziamenti alla clientela e finanziamenti commerciali. Il gigante della tecnologia è anche coinvolto nel calcolo quantistico tramite la sua IBM Quantum Platform, che offre accesso pubblico e premium ai suoi servizi di calcolo quantistico basati su cloud. Questi includono un set di prototipi di processori quantistici IBM, tutorial sul calcolo quantistico e un libro di testo interattivo.

Più recentemente, gli scienziati IBM ha dichiarato che sono un altro passo avanti verso il superamento di un ostacolo che sblocca il potenziale rivoluzionario dei computer quantistici. Per questo, hanno introdotto un nuovo codice quantistico di correzione degli errori, che secondo loro è circa dieci volte più efficiente dei metodi precedenti. 

Alla fine dell’anno scorso, la società ha anche lanciato il computer quantistico chiamato Condor, con 1,121 qubit superconduttori disposti a nido d’ape. IBM ha inoltre presentato IBM Quantum System Two, il suo primo computer quantistico modulare e un'architettura di supercalcolo incentrata sui quanti, che è scalabile e quindi può essere aggiornato con chip che saranno lanciati nei prossimi cinque anni.

Con una capitalizzazione di mercato di 175 miliardi di dollari, le azioni IBM sono scambiate a 190.86 dollari, in rialzo del 16.66% da inizio anno. IBM ha registrato un fatturato (TTM) di 61.86 miliardi di dollari, con un utile per azione (TTM) di 8.03, un rapporto prezzo/utili (TTM) di 23.76 e un ROE (TTM) del 33.36%. La società paga un rendimento da dividendi del 3.48%.

#2. D-Wave Systems

Questa società di informatica quantistica sviluppa e fornisce sistemi, software e servizi correlati. I suoi prodotti includono The Leap e The Advantage e fornisce applicazioni quantistiche per la pianificazione, la logistica, la scoperta di farmaci, i processi di produzione e altro ancora. 

All’inizio di questo mese, D-Wave ha affermato che le macchine quantistiche ora possono risolvere problemi con applicazioni del mondo reale più velocemente di qualsiasi normale computer. All’inizio di quest’anno, la società ha annunciato un computer quantistico con 1,200 qubit, 10,000 accoppiatori e un tempo di risoluzione 20 volte più veloce su problemi difficili di ottimizzazione.

Le azioni della società sono attualmente scambiate a 1.86 dollari, in rialzo del 138.6% da inizio anno (YTD), con una capitalizzazione di mercato di 267 milioni di dollari. Ha registrato un fatturato di 8.247 milioni di dollari (TTM), un utile per azione (EPS) di -0.66 (TTM) e un rapporto prezzo/utili (P/E) di -3.19 (TTM), e ha annunciato una crescita del fatturato di oltre il 20% sia per i risultati del quarto trimestre che per quelli di fine anno 4, mentre le prenotazioni sono aumentate rispettivamente del 2023% e dell'34%. 

È interessante notare che il CEO dell'azienda, il dott. Alan Baratz, ha dichiarato lo slancio dell'azienda, citando la partnership strategica pluriennale con Zapata AI, l'introduzione del prototipo Advantage1,200 da oltre 2 qubit, le joint venture con NEC Australia e Deloitte Canada e la nomina dell'ex Segretario per la Sicurezza Nazionale Kirstjen Nielsen al consiglio di amministrazione.

Conclusione

Si prevede che il mercato dell’informatica quantistica lo farà raggiungere $ 6.5 miliardi nel 2028, e il suo potenziale per risolvere il problema del commesso viaggiatore (TSP) ha ramificazioni per diversi settori, come la produzione, la logistica, la gestione della catena di fornitura, l’e-commerce, i trasporti e la ricerca. Dopotutto, può portare benefici sostanziali, in particolare aumentando la produttività, tagliando le spese e stimolando l’innovazione in diversi settori.

Fai clic qui per l'elenco delle cinque migliori società di informatica quantistica.