Solving The Travelling Salesman Problem Using A Single Qubit

Sintesi Tecnica: Risolvere il Problema del Commesso Viaggiatore Utilizzando un Singolo Qubit

Enunciato del Problema
Il Problema del Commesso Viaggiatore (TSP - Travelling Salesman Problem) è un problema di ottimizzazione combinatoria fondamentale, di classe NP-difficile, che richiede l'identificazione del percorso più breve possibile che visiti un insieme di città esattamente una volta e ritorni all'origine. Sebbene esistano algoritmi classici, le soluzioni esatte scalano esponenzialmente con il numero di città, e i metodi euristici non garantiscono l'ottimalità. Gli approtti quantistici esistenti, come quelli che utilizzano l'Ottimizzazione Binaria Non Vincolata Quadratica (QUBO) mappata su Hamiltoniane di Ising o circuiti di stima della fase, sono dispendiosi in termini di risorse. Essi richiedono tipicamente un gran numero di qubit (ad esempio, migliaia di qubit fisici per un problema di 10 città) e spesso soffrono di basse probabilità di successo su hardware rumorosi attuali.

Metodologia
Gli autori propongono un algoritmo che mappa un arbitrario TSP su un singolo qubit, sfruttando il principio del parallelismo quantistico piuttosto che dell'entanglement. La metodologia principale si articola in tre fasi principali:

1. Mappatura in un Problema di Brachistocrona Discreta:
   Il TSP viene prima riformulato come un problema di Brachistocrona discreta finita. In questa analogia classica, le città sono rappresentate come punti su un piano 2D e i percorsi sono funzioni lineari a tratti. L'obiettivo è minimizzare un funzionale del tempo $Q$, che corrisponde alla distanza totale di percorrenza. Il problema è vincolato dal fatto che il percorso debba tornare alla città iniziale, codificato da un segmento lineare aggiuntivo verso un punto finale $F$.

2. Codifica sulla Sfera di Bloch:
   Il problema della Brachistocrona discreta viene mappato sulla geometria della sfera di Bloch di un singolo qubit.

• Rappresentazione dello Stato: Le città ($c_i$) sono rappresentate da stati quantistici $|P_{ii}\rangle$ situati sull'equatore della sfera di Bloch.
• Codifica della Distanza: Le distanze relative tra le città sono codificate come distanze geometriche (geodetiche) sulla sfera. Gli stati intermedi $|P_{ij}\rangle$ sono posizionati su curve geodetiche che collegano gli stati equatoriali a un polo $P_0$. La distanza angolare tra gli stati corrisponde alla distanza euclidea tra le città.
• Percorrenza: Il movimento tra le città avviene tramite operatori di rotazione ($U^u$ e $U^d$). Un "passo" da una città $i$ a una città $j$ comporta una rotazione "su" dall'equatore verso uno stato intermedio $|P_{ij}\rangle$ (più vicino al polo) seguita da una rotazione "giù" verso lo stato equatoriale $|P_{jj}\rangle$.

3. Ottimizzazione Quantistica tramite Sovrapposizione:
   A differenza di un approccio brute-force che percorre i cammini sequenzialmente, l'algoritato proposto utilizza la sovrapposizione quantistica per attraversare più percorsi simultaneamente.

• Creazione della Sovrapposizione: Il sistema viene inizializzato in uno stato corrispondente alla città di partenza. Una serie di operatori di rotazione regolabili crea uno stato di sovrapposizione ad ogni livello della tabella di marcia (routing chart), esplorando efficacemente tutti i percorsi validi e non validi contemporaneamente.
• Ottimizzazione: L'algoritmo impiega metodi di controllo ottimale, specificamente la Perturbazione Stocastica di Approssimazione Simultanea (SPSA), per regolare gli operatori di rotazione.
• Funzione Obiettivo: Mentre un approccio quantistico brute-force potrebbe minimizzare un funzionale del tempo $T$, l'approccio basato sulla sovrapposizione minimizza la funzione di costo classica $D$ (distanza totale). Ciò è necessario perché la sovrapposizione include percorsi "classicamente proibiti" che non formano cicli hamiltoniani validi. L'ottimizzazione cerca di massimizzare la popolazione del ciclo hamiltoniano valido nello stato finale.
• Misurazione e Post-elaborazione: L'algoritmo si conclude con una misurazione proiettiva dello stato penultimo. Attraverso la tomografia dello stato quantistico, la distribuzione della popolazione viene analizzata per identificare il percorso dominante, che corrisponde al percorso ottimale del TSP.

Risultati Chiave
Gli autori presentano simulazioni numeriche che risolvono istanze di TSP con 4-9 città utilizzando un singolo qubit.

• Accuratezza: Per le dimensioni dei problemi testate, l'algoritmo ha ottenuto soluzioni esatte (rapporto di approssimazione $\sim 1$) per più del 90% delle istanze del problema.
• Approssimazione: Nei casi in cui non sono state trovate soluzioni esatte, l'algoritmo ha raggiunto elevati rapporti di approssimazione ($\sim 0,90$).
• Efficienza delle Risorse: Il metodo richiede un solo qubit, un netto contrasto con gli algoritmi quantistici esistenti che richiedono centinaia o migliaia di qubit per problemi simili.
• Agnosticismo della Piattaforma: L'algoritmo è progettato per essere implementabile su qualsiasi piattaforma quantistica capace di rotazioni di qubit arbitrari ad alta fedeltà e tomografia dello stato, inclusi qubit superconduttori, ioni intrappolati, centri azoto-vacanza e atomi di Rydberg.

Significatività e Rivendicazioni
L'articolo sostiene che questo approccio offra un'alternativa più efficiente in termini di risorse e più accurata rispetto agli algoritoli quantistici esistenti per istanze di TSP di piccole-medie dimensioni. Utilizzando il principio di sovrapposizione su un singolo qubit, il metodo evita la necessità di grandi scale di entanglement e di estese conte di qubit, affrontando uno dei principali colli di bottiglia dell'attuale hardware quantistico.

Gli autori discutono un potenziale aumento della velocità polinomiale rispetto agli algoritmi classici, suggerendo che il parallelismo quantistico inerente alla sovrapposizione dei percorsi possa fornire un vantaggio pratico sia in termini di tempo che di accuratezza. Il lavoro posiziona il TSP non solo come un problema di routing, ma come un caso specifico di problema di Brachistocrona vincolato risolvibile tramite controllo quantistico, aprendo una via per l'ottimizzazione quantistica scalabile su dispositivi a breve termine (near-term devices).