Come può un computer quantistico risolvere il problema del venditore viaggiatore?

Il problema del venditore viaggiatore (TSP) chiede di trovare il percorso più corto che visita una serie di città una sola volta. Tradizionalmente, risolverlo richiede un’enorme potenza di calcolo, perché il numero di possibili percorsi cresce esponenzialmente. In un nuovo studio, gli scienziati hanno proposto un metodo per “codificare” il TSP su un computer quantistico usando l’amplitude encoding. In pratica, le informazioni su tutte le città vengono rappresentate in uno stato quantistico con un numero di qubit che cresce solo in modo logaritmico rispetto al numero di città, quindi con pochi qubit si può descrivere un problema molto grande.

Per valutare la lunghezza del percorso, invece di sommare le aspettative di diversi operatori quantistici (come si fa di solito), gli autori usano una funzione non lineare degli stessi valori di aspettazione. Questo approccio permette di ottenere la distribuzione di probabilità del costo direttamente dal computer quantistico. Il tutto è stato testato con un algoritmo chiamato variational quantum eigensolver (VQE), che combina una rete di parametri quantistici con una classica routine di ottimizzazione. Il risultato? Il VQE è riuscito a trovare il percorso più breve su diversi grafi, dimostrando che il metodo funziona su un’ampia gamma di iper‑parametri di ottimizzazione. In sostanza, la ricerca suggerisce che i futuri computer quantistici potrebbero affrontare problemi di ottimizzazione complessi con risorse molto più contenute rispetto ai computer classici.

L’amplitude encoding sfrutta la capacità dei qubit di rappresentare simultaneamente 2^n stati, dove n è il numero di qubit. Codificando le città in una base logaritmica, si riduce drasticamente la dimensione della registrazione rispetto a una codifica binaria tradizionale. La funzione di costo non lineare proposta si basa su una combinazione di operatori di proiezione che, una volta misurati, forniscono una distribuzione di probabilità p(i) associata a ciascun percorso i. Il valore atteso della lunghezza del percorso è quindi Σ_i L_i p(i), dove L_i è la lunghezza del percorso i. Tuttavia, anziché calcolare direttamente Σ_i L_i p(i), gli autori applicano una trasformazione non lineare f(⟨O⟩) che enfatizza le configurazioni a basso costo, migliorando la convergenza dell’algoritmo VQE. Il VQE utilizza un ansatz parametrico, tipicamente una serie di porte rotazionali e entanglement a coppie, ottimizzato mediante gradienti o metodi di ricerca bayesiana. Gli iper‑parametri chiave includono la profondità dell’ansatz, il tasso di apprendimento dell’ottimizzatore classico e il numero di misurazioni (shots) per stima delle aspettative. I risultati mostrano che, entro un ampio intervallo di questi parametri, il VQE converge verso la soluzione ottimale, suggerendo una certa robustezza del metodo rispetto a rumore e imperfezioni hardware. Questo approccio apre la strada a implementazioni su dispositivi quantistici NISQ, dove la riduzione del numero di qubit e la tolleranza agli errori sono cruciali per la scalabilità.