Ogni giorno migliaia di corrieri lasciano i propri magazzini scegliendo il percorso che reputano più efficiente tra migliaia di punti di consegna (PdC). La soluzione di questo rompicapo è in buona misura ispirata al cosiddetto Problema del Commesso Viaggiatore (o TSP), che risponde alla domanda: dato un reticolo stradale, qual è il percorso migliore da percorrere, in grado di collegare tutti i punti di consegna e passando una sola volta per ciascuno di questi?
Indice degli argomenti
Calcolo quantistico e logistica urbana: il contesto operativo
Non è possibile trovare soluzione esatta a questo problema senza esplorare, a priori, tutti i cammini possibili.
Intendiamoci: trovare soluzioni a problemi reali tramite astrazioni matematiche non è mai immediato. I reticoli stradali, ad esempio, nascondono strade chiuse e interruzioni di percorso; i corrieri lottano quotidianamente con limiti di tempo, traffico e carburante, che non consentono di ricorrere a soluzioni di problemi matematici del tutto generali.
Ciononostante, la soluzione del TSP, pur essendo solo un tassello per la soluzione di problemi più ampi, potrebbe rappresentare uno degli ambiti in cui il Quantum Computing potrebbe trasformarsi in un game changer, per la sua capacità di elaborare soluzioni a problemi di complessità crescente in tempi relativamente ridotti.
Sperimentazioni reali e progettualità nel calcolo quantistico
In generale risolvere problemi simili su larga scala e in tempi brevi, permetterebbe di ottimizzare i servizi di logistica, rendendo ad esempio più efficiente il consumo di carburante, la pianificazione delle rotte e potrebbe ridurre i costi di esercizio.
Su queste sfide lavora il progetto Quantum Computing for Efficient Urban Logistical Ecosystem finanziato nell’ambito dell’ICSC – Centro Nazionale di Ricerca in High Performance Computing, Big Data and Quantum Computing – finanziato con fondi PNRR Il progetto mira a sfruttare il Calcolo Quantistico per affrontare problemi chiave della logistica urbana come quello del commesso viaggiatore ma anche del routing dei veicoli, con l’obiettivo di ottimizzare processi complessi quali la raccolta dei rifiuti, la consegna dell’ultimo miglio e la gestione di interventi di manutenzione.
Algoritmi classici e quantistici nella logistica urbana
Ma cosa significa, in concreto, affrontare un problema come il TSP con il quantum computing? Tutto parte dal modo in cui costruiamo (e combiniamo) gli algoritmi.
Trasformare un problema classico in un analogo quantistico non è semplice e ad oggi esistono diversi approcci per farlo. Il primo passo, probabilmente il più complesso, è quello di scomporre il fenomeno in problemi più semplici, alcuni dei quali risolvibili quantisticamente. La soluzione tecnica va poi implementata in codice, come normalmente si farebbe con un software tradizionale. Esistono strumenti teorici per farlo, ma anche semilavorati, framework open source e librerie disponibili in rete, che distillano anni di ricerca e sforzi in ambito accademico e industriale.
Il framework Qiskit, realizzato da IBM è uno dei framework di sviluppo più conosciuti. Una volta messo a punto il programma, questo può essere eseguito accodandone l’esecuzione su una macchina quantistica, deputata all’esecuzione del calcolo.
L’esperienza ci insegna che gli strumenti software disponibili pubblicamente consentono di implementare soluzioni anche molto complesse in linguaggi di programmazione noti per la loro semplicità e versatilità (come Python, ad esempio), ma sono lungi dall’essere sufficienti, da soli, per risolvere un problema ispirato al TSP in uno scenario reale.
Per soddisfare i vincoli a cui concretamente i corrieri sono sottoposti, è necessario combinare con creatività ed esperienza algoritmi di natura diversa, basati sia su tecniche quantistiche, che su approcci avanzati più tradizionali, come Clustering, Graph Analytics ecc.
Il ruolo del cloud per il calcolo quantistico applicato
Gran parte degli algoritmi quantistici è pensato per effettuare calcoli su risorse hardware quantistiche, che sono collocate in pochi laboratori in tutto il mondo, e sono concentrati in alcuni Paesi senza seguire veri e propri standard costruttivi e su principi fisici differenti (superconduttivi, fotonici, trapped ion, ecc). A caratteristiche costruttive diverse corrisponderebbero in teoria requisiti e tecniche realizzative diverse.
Per sopperire alla scarsità di risorse e alla loro dispersione geografica, ci viene in aiuto il paradigma del Cloud, grazie al quale abbiamo perfezionato modelli di lavoro formidabili, ampiamente collaudati in molti campi, dalla gestione di storage remoto al calcolo distribuito. Per questo oggi, insieme all’hardware, molti vendor mettono a disposizione portali di gestione di risorse Quantum graficamente accattivanti e API per la programmazione. Questo aggiunge un livello di astrazione software che consente di gestire da remoto la propria infrastruttura, come se si trattasse di un database, o di un qualunque servizio di traduzione linguistica.
Simulazioni quantistiche e infrastrutture HPC nella logistica
Una volta risolto il problema di accedere a macchine quantistiche ed eseguirvi codice, resta un ultimo nodo da sciogliere: ad oggi l’hardware a disposizione su larga scala soffre di margini di errori ancora non trascurabili quando si tratta di risolvere problemi di alta complessità come il TSP, e sconta oneri economici piuttosto elevati, che ne rendono poco pratico l’uso. Per dare un’idea, in diverse sperimentazioni che abbiamo svolto su hardware quantistico, il costo di un semplice “esperimento” su macchine quantistiche “gate-based” si aggirava intorno a pochi centesimi di euro. D’altronde, i processi quantistici non sono perfettamente deterministici, ma sono governati da leggi statistiche. Poiché il risultato di un processo quantistico può variare di volta in volta, possono essere necessari migliaia di esperimenti identici per calcolare la soluzione di un problema.
Ciò rende l’uso dei computer quantistici conveniente per la soluzione su problemi di vasta scala, ma non necessariamente su problemi semplici, che potrebbero essere risolti a basso prezzo anche sfruttando hardware tradizionale. Per questo motivo, spesso si ricorre ad ambienti di simulazione, piuttosto che utilizzare direttamente hardware quantistico. Queste macchine permettono di replicare in modo semplificato su hardware classico condizioni analoghe a quelle di un sistema quantistico reale, approfondendone i risultati, nella prospettiva che possano essere presto implementati su larga scala. Generalmente, le simulazioni si avvalgono di risorse HPC (High Performance Computing), in particolare GPU (Graphical Processing Unit), che sono ottimizzate per il calcolo matriciale, elemento fondamentale sia per i modelli di Intelligenza Artificiale che per quelli di computazione quantistica.
La stima delle risorse necessarie per terminare con successo il calcolo richiede tuttavia un importante mix di competenze tecniche (conoscenza dei limiti delle infrastrutture e di tecniche di integrazione tra infrastrutture di calcolo), quantistiche (valutare la dimensione del problema, in termini di qubit) e analitiche (analizzare le metriche necessarie al raggiungimento dei risultati).
Mentre negli ultimi mesi anche in Italia diverse istituzioni (Cineca, Politecnico di Milano, Università di Napoli) hanno iniziato a dotarsi di Macchine Quantistiche, infrastrutture HPC come quelle offerte da CINECA continuano a giocare un ruolo cruciale come risorse vitali per la sperimentazione. In un contesto come quello del TSP, se un singolo nodo dell’infrastruttura Leonardo (uno delle più potenti infrastrutture al mondo e, ad oggi, la prima in Europa) permette solo la simulazione di un processo relativamente semplice (pochi punti di consegna), l’uso collaborativo di più nodi di calcolo consente di trovare soluzioni evolute grazie ad architetture algoritmiche ibride (classico-quantistiche) e più complesse.
Il potenziale futuro del calcolo quantistico per la logistica urbana
Se quindi il Calcolo Quantistico è per molti aspetti una tecnologia in fase di maturazione, sono evidenti il suo potenziale strategico per affrontare problemi ad alta complessità e le sue ricadute sul mondo delle tecnologie digitali. In attesa di poter disporre su più vasta scala di hardware quantistico, su una infrastruttura coordinata a livello Nazionale ed Europeo, Algoritmi, Cloud e Calcolo HPC restano le tre direttrici abilitanti che guidano lo sviluppo e ne rendono possibile la sperimentazione. Investire ora in competenze, infrastrutture e modelli ibridi significa prepararsi con pragmatismo e visione a un futuro in cui il Quantum rivoluzionerà le nostre capacità di calcolo e di costruzione di nuove applicazioni.
