Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Immaginate un autista di consegne che deve visitare un elenco di città esattamente una volta e tornare a casa, puntando a percorrere la distanza più breve possibile. Questo è il problema del commesso viaggiatore, un classico enigma che sta al cuore della logistica, della pianificazione e della progettazione di circuiti. Se trovare il percorso perfetto per poche città è facile, la difficoltà esplode man mano che l'elenco cresce; per ogni nuova città aggiunta, il numero di percorsi possibili si moltiplica così rapidamente che persino i supercomputer più veloci possono rimanere bloccati nel tentativo di trovare quello migliore. Per decenni, gli scienziati si sono rivolti ai computer quantistici, macchine che utilizzano le strane regole delle particelle subatomiche per elaborare informazioni, per risolvere questi enigmi. Tuttavia, un ostacolo principale è rimasto: come tradurre il problema in un linguaggio che il computer quantistico comprenda senza annegare il calcolo in errori e complessità superflue.

Un ricercatore presso QuantScape Inc. ha ora dimostrato un nuovo modo per guidare un computer quantistico attraverso questo labirinto, trovando con successo il percorso più breve per mappe con fino a dieci città. Il lavoro, che si basa su simulazioni di hardware quantistico piuttosto che su macchine fisiche, introduce un metodo che utilizza molti meno bit quantistici — le unità di base dell'informazione in un computer quantistico — rispetto alle precedenti approcci. Ancora più importante, mostra che un singolo insieme di istruzioni può adattarsi a condizioni stradali mutevoli, come il traffico che varia durante il giorno, senza dover essere riaddestrato per ogni nuovo scenario. I risultati suggeriscono che, con la giusta codifica e tecniche di addestramento, i computer quantistici potrebbero presto affrontare problemi di ottimizzazione che sono attualmente fuori portata, a condizione che l'hardware continui a migliorare.

La sfida centrale risiede nel modo in cui il problema viene scritto per la macchina. I metodi tradizionali assegnano un bit quantistico separato a ogni possibile combinazione di una città e una posizione nel percorso. Per una mappa con dieci città, questo approccio richiede ottantuno bit, e costringe il computer a controllare e scartare costantemente percorsi non validi, sprecando tempo ed energia in penalità. Il nuovo studio utilizza una strategia diversa, ispirata a un sistema matematico chiamato codice di Lehmer, che essenzialmente classifica ogni possibile percorso in base al suo ordine in un elenco. Questo metodo richiede solo diciannove bit per dieci città, una riduzione significativa. Utilizzando questo codice compatto, ogni stato del computer quantistico rappresenta un percorso valido, eliminando la necessità di controlli di penalità. Per rendere la ricerca efficiente, i ricercatori hanno disposto questi stati in modo che il ribaltamento di un singolo bit nel codice corrisponda a un cambiamento piccolo e logico nel percorso, permettendo al computer di esplorare lo spazio delle soluzioni in modo fluido.

Per guidare il computer quantistico, i ricercatori hanno impiegato un sistema ibrido chiamato rete Kolmogorov–Arnold quantistica variazionale. Pensate a questo come a un controller intelligente che osserva la mappa e l'ora del giorno, poi imposta i cursori del circuito quantistico sulle posizioni corrette. Invece di codificare rigidamente le impostazioni per ogni specifica mappa, questo controller impara una regola generale: come regolare il circuito in base alle distanze tra le città e all'ora corrente. Ciò consente al sistema di gestire grafi dipendenti dal tempo, dove i tempi di percorrenza cambiano, come una rete elettrica o una rete stradale durante l'ora di punta. Il controller è stato addestrato con un obiettivo specifico: minimizzare il rischio di scegliere un percorso lungo. Piuttosto che cercare solo la lunghezza media assoluta, l'addestramento si è concentrato sugli scenari peggiori all'interno del top pochi percentuali di risultati probabili, garantendo che il risultato finale sia robusto e affidabile.

Il processo di addestramento stesso è stato rigoroso, progettato per evitare la trappola comune di incastrarsi in un minimo locale, dove il computer si accontenta di una risposta "abbastanza buona" invece della migliore. I ricercatori hanno utilizzato una strategia in più fasi che partiva da ricerche ampie e si restringeva gradualmente, combinata con una tecnica che scuoteva deliberatamente le impostazioni per uscire dai vicoli ciechi. Hanno anche utilizzato un metodo chiamato basin hopping, che agisce come una leggera scossa per aiutare il sistema a saltare fuori da valli poco profonde nella ricerca. Testato su mappe con quattro a dieci città, inclusi forme simmetriche e reti casuali e irregolari, questo approccio ha trovato il percorso perfetto in ogni singolo caso per le mappe più piccole. Per le mappe a dieci città, significativamente più difficili, il metodo ha trovato il percorso ottimale in 112 casi su 120, con i fallimenti rimanenti che erano solo dell'uno percento rispetto alla distanza perfetta.

Fondamentalmente, lo studio ha escluso diverse idee alternative che potevano sembrare promettenti. I ricercatori hanno testato un approccio più semplice che utilizza solo dieci bit, uno per ogni città, per tracciare la posizione del conducente passo dopo passo. Questo metodo è fallito completamente per mappe con sei o più città perché non riusciva a rappresentare le complesse relazioni tra le tappe successive. Hanno anche confrontato i loro risultati con un algoritmo classico standard noto come 2-opt, che migliora un percorso scambiando due segmenti. Sebbene il 2-opt sia efficace, il circuito quantistico ha fornito un punto di partenza molto migliore, e la combinazione dei due ha superato entrambi i metodi presi singolarmente. Lo studio ha confermato che il successo derivava dal modo specifico in cui il problema era codificato e dal sofisticato addestramento del controller, non solo dalla potenza del circuito quantistico stesso.

Le scoperte evidenziano anche l'efficienza del metodo riguardo alla misurazione. In un vero computer quantistico, leggere la risposta richiede di ripetere il processo molte volte per ottenere un segnale chiaro. Le simulazioni hanno mostrato che anche con appena cento letture, il sistema poteva identificare in modo affidabile il percorso migliore. Ciò suggerisce che, quando saranno disponibili computer quantistici fisici con abbastanza bit, questo metodo potrà fornire risultati rapidamente senza richiedere milioni di ripetizioni. I ricercatori hanno notato che, sebbene l'attuale lavoro sia stato eseguito su un computer classico che simula il comportamento quantistico, le tecniche sono progettate per funzionare su hardware reale. I passi successivi prevedono il test del sistema nelle condizioni rumorose delle macchine reali e la sua scalabilità su mappe più grandi dove il numero di percorsi possibili è troppo vasto per essere controllato a mano.

Questo lavoro rappresenta un passo avanti significativo nel rendere pratica l'ottimizzazione quantistica. Risolvendo il problema della codifica e creando un controller che si generalizza attraverso diverse mappe e tempi, i ricercatori hanno mostrato una via per rendere i computer capaci di risolvere problemi di instradamento complessi in modo efficiente. La capacità di gestire cambiamenti dipendenti dal tempo con un unico insieme di parametri è particolarmente promettente per le applicazioni del mondo reale dove le condizioni non sono mai statiche. Sebbene il viaggio verso un ottimizzatore quantistico pienamente funzionale sia in corso, questo studio fornisce una chiara tabella di marcia su come addestrare queste macchine per trovare il percorso più breve attraverso un mondo complesso.