Processo di Markov a eco quantistica per l’ottimizzazione combinatoria

Abstract degli autori

Introduciamo un processo di Markov a eco quantistica per l’ottimizzazione combinatoria. La dinamica quantistica basata sull’annealing quantistico (QA) o sull’algoritmo quantistico approssimato di ottimizzazione (QAOA) viene usata per progettare il kernel di transizione. Aumentare il tempo di annealing nel QA o il numero di layer nel QAOA consente alle transizioni di esplorare configurazioni distanti, sopprimendo al contempo le grandi variazioni di energia. La delocalizzazione nello spazio di Hamming deriva dalla diffusione degli operatori, mentre la localizzazione nello spazio energetico è dovuta a una correlazione generata dinamicamente. Per l’ottimizzazione, proponiamo un’ottimizzazione locale a eco quantistica, con e senza discesa greedy. Riscontriamo che le sue prestazioni sono determinate dall’interazione tra la non località nello spazio di Hamming e la località nello spazio energetico, e che un’eccessiva localizzazione nello spazio energetico può degradare le prestazioni dell’ottimizzazione. L’integrazione della discesa greedy migliora notevolmente le prestazioni, evidenziando i ruoli complementari della dinamica quantistica nell’esplorazione e della discesa greedy nello sfruttamento. Questi risultati stabiliscono la dinamica a eco quantistica come un quadro di riferimento per progettare kernel di transizione strutturati e offrono un percorso per utilizzare la dinamica quantistica a molti corpi con risorse finite come primitiva computazionale per l’ottimizzazione iterativa.