Accelerazioni quantistiche superquadratiche per l’ottimizzazione combinatoria tramite cammini inclinati

Abstract degli autori

Introduciamo i cammini quantistici inclinati, un framework algoritmico quantistico per risolvere problemi di ottimizzazione combinatoria esatta. Il framework applica una media di potenze di un’Hamiltoniana inclinata, che modifica la matrice discriminante di una catena di Markov di base (mixer) mediante la funzione obiettivo. Il nostro punto di partenza sono gli algoritmi quantistici a cammino breve, che preparano lo stato fondamentale di una simile Hamiltoniana e ottengono accelerazioni superquadratiche rispetto alla ricerca esaustiva per alcuni problemi di ottimizzazione combinatoria. Di recente, Le Gall e Tamaki~(arXiv:2604.12131) hanno sviluppato un algoritmo classico basato su condizionamento e ricerca per MAX-E$k$-LIN2 pesato e MAX-$k$-CSP pesato. Sotto le stesse ipotesi, il loro algoritmo è più lento di un fattore soltanto subquadratico rispetto agli algoritmi quantistici a cammino breve. Di conseguenza, gli algoritmi a cammino breve esistenti non dimostrano un’accelerazione superquadratica rispetto a questa baseline classica più forte. Per i problemi di massimizzazione, forniamo condizioni in cui i cammini inclinati aumentano l’ampiezza dello stato bersaglio con un valore obiettivo elevato, quando si parte da uno stato iniziale con un valore obiettivo inferiore. Questo framework comprende il condizionamento e la ricerca e consente di ottenere accelerazioni superquadratiche rispetto a tale approccio per gli stessi problemi. Sebbene il nostro framework recuperi gli algoritmi quantistici a cammino breve come caso particolare, non richiede né la preparazione dello stato fondamentale né l’inizializzazione nello stato fondamentale del mixer di base. Mostriamo questi vantaggi su un problema di ottimizzazione sintetico, per il quale i cammini inclinati ottengono un’accelerazione superquadratica, mentre gli algoritmi a cammino breve non la ottengono.