Quantum circuit evolutionary framework applied on set partitioning problem

Sintesi Tecnica: Framework Evolutivo di Circuiti Quantistici Applicato al Problema di Partizionamento degli Insiemi

Definizione del Problema
Il documento affronta il Problema di Partizionamento degli Insiemi (SPP), una sfida ben nota di ottimizzazione combinatoria NP-dura. Lo SPP consiste nel dividere un insieme di elementi in sottoinsiemi mutualmente esclusivi ed esaustivi per minimizzare il peso totale, garantendo che ogni elemento appartenga esattamente a un sottoinsieme. Le applicazioni pratiche includono la programmazione degli equipaggi aerei. Per risolvere questo problema su hardware quantistico, gli autori formulano lo SPP come un problema di Ottimizzazione Binaria Quadratica Senza Vincoli (QUBO), che viene successivamente mappato su un Hamiltoniano di Ising. Lo studio mira specificamente alle limitazioni degli attuali Algoritmi Quantistici Variazionali (VQA), come il Variational Quantum Eigensolver (VQE), che spesso soffrono di "barren plateaus" (altipiani sterili)—un fenomeno in cui i gradienti svaniscono esponenzialmente all'aumentare del numero di qubit, portando a una stagnazione della convergenza.

Metodologia
Gli autori propongono un framework Quantum Circuit Evolutionary (QCE) che si discosta dall'approccio VQE standard. A differenza del VQE, che utilizza una topologia di circuito fissa (ansatz) con parametri variabili ottimizzati da un ottimizzatore classico, il framework QCE evolve la topologia del circuito stesso. Lo studio valuta due strategie distinte all'interno di questo framework:

1. Evoluzione di Circuiti Quantistici Senza Ansatz (AF-QCE):

   • Ispirata alla letteratura precedente [13], questo approccio inizia con un circuito minimale (una singola porta casuale) ed evolve iterativamente senza un ansatz predefinito.
   • L'evoluzione si basa su operazioni di mutazione: INSERT (aggiungere una porta), DELETE (rimuovere una porta), SWAP (sostituire una porta) e MODIFY (regolare i parametri della porta).
   • Viene generata una popolazione di circuiti, misurata e il circuito con le prestazioni migliori viene selezionato come genitore per la generazione successiva, garantendo una riduzione monotona della funzione di costo.

2. Ansatz con Termine Evolutivo Pseudo-Controadiabatico (APCD-QCE):

   • Questo approccio incorpora una struttura ispirata alla fisica nell'ansatz per migliorare la convergenza. Utilizza un Hamiltoniano $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$, dove $H_{ad}$ rappresenta un Hamiltoniano di evoluzione temporale adiabatica e $H_{pcd}$ è un termine evolutivo pseudo-controadiabatico.
   • L'operatore unitario è definito come $U = U_{ad}U_{pcd}$. Il componente $U_{ad}$ è fisso (un passo di Trotter), mentre $U_{pcd}$ viene evoluto utilizzando la stessa strategia di mutazione evolutiva dell'AF-QCE.
   • La preparazione dello stato iniziale utilizza $|+\rangle^{\otimes n}$ e vengono applicate impostazioni parametriche specifiche ($\beta=0, \delta=0.5$) per facilitare l'esplorazione dello spazio di Hilbert.

Setup Sperimentale
Gli esperimenti sono stati condotti utilizzando la libreria Qiskit su un simulatore ad alte prestazioni (KUATOMU) in due scenari:

• Senza Rumore: Sono stati testati 35 istanze dello SPP (da 6 a 20 qubit).
• Con Rumore: Le simulazioni includevano canali di errore depolarizzanti ($\epsilon = 0.01$) su qubit specifici per mimare le limitazioni dei dispositivi NISQ.
• Confronto: Le strategie QCE sono state confrontate con il VQE standard (utilizzando un ansatz di entanglement lineare a due locali e l'ottimizzatore COBYLA).
• Metrica: Le prestazioni sono state misurate utilizzando il Rapporto di Approssimazione ($R$), definito come il rapporto tra un valore di riferimento classico (risolutore Gurobi) e il valore di aspettazione minimo trovato dall'algoritmo quantistico.

Risultati Chiave

• Superiorità rispetto al VQE: In scenari senza rumore, sia AF-QCE che APCD-QCE hanno superato significativamente il VQE. Le prestazioni del VQE si sono degradate rapidamente all'aumentare del numero di qubit (spesso fallendo nella convergenza per istanze $\ge 10$ qubit), mentre gli approcci evolutivi hanno mantenuto prestazioni migliori.
• Prestazioni di APCD-QCE: La strategia APCD-QCE ha dimostrato i risultati più robusti, raggiungendo un rapporto di approssimazione di 1,00 (ottimale) in 25 casi su 35. Ha efficacemento evitato la stagnazione della convergenza nella maggior parte dei casi in cui VQE e AF-QCE faticavano.
• Limiti di Scalabilità: Nonostante i miglioramenti, le sfide di scalabilità sono persistite. Per le istanze a 20 qubit (specificamente 20.1, 20.6 e 20.7), tutti i metodi, incluso APCD-QCE, hanno mostrato segni di stagnazione della convergenza, con un calo significativo dei rapporti di approssimazione.
• Impatto del Rumore: Nelle simulazioni con rumore, le prestazioni sono peggiorate per tutti gli algoritmi, in particolare nelle istanze più piccole. Tuttavia, i framework QCE hanno generalmente mantenuto prestazioni comparabili o migliori rispetto al VQE.

Significato e Affermazioni
Il documento afferma che il framework QCE proposto offre un'alternativa promettente agli algoritmi variazionali a ansatz fisso per problemi di ottimizzazione intera. I contributi chiave includono:

• Mitigazione della Stagnazione: Il framework, in particolare la variante APCD-QCE, dimostra una notevole capacità di evitare la stagnazione della convergenza associata agli altipiani sterili nei VQA standard.
• Eliminazione degli Ottimizzatori Classici: Evolvendo direttamente la topologia del circuito, la procedura evita la necessità di ottimizzatori classici (come COBYLA) per regolare i parametri, affrontando un collo di bottiglia nei flussi di lavoro VQA attuali.
• Percorso verso la Scalabilità: Sebbene non sia una soluzione completa alla stagnazione a 20 qubit, i risultati suggeriscono che i circuiti a topologia variabile offrono una "strada interessante" per risolvere problemi di ottimizzazione su larga scala. Gli autori notano che la strategia APCD-QCE è "quasi immune" agli effetti di stagnazione della convergenza dato un numero sufficientemente elevato di generazioni, sebbene l'uscita dai minimi locali nel paesaggio di mutazione rimanga una sfida.

Gli autori concludono che, sebbene il metodo affronti ostacoli di scalabilità con l'aumento del numero di qubit, l'integrazione di termini ispirati alla fisica (pseudo-controadiabatici) nella ricerca evolutiva di circuiti produce risultati incoraggianti per la risoluzione di problemi combinatori su dispositivi NISQ.