Benchmarking Adaptative Variational Quantum Algorithms on QUBO Instances

Questo articolo presenta un benchmark sistematico di tre algoritmi quantistici variazionali adattivi (EVQE, VAns e RA-VQE) rispetto al QAOA su problemi QUBO, analizzando la qualità delle soluzioni, i tempi di calcolo e l'impatto dei parametri per fornire linee guida per l'ottimizzazione su dispositivi quantistici NISQ.

L'essenziale

Immagina di dover risolvere un enorme puzzle (un problema di ottimizzazione) usando un robot molto speciale: un computer quantistico.

Il Problema: Il Robot "Rigido"

Fino a poco tempo fa, questi robot quantistici erano come costruttori di Lego che avevano un solo manuale di istruzioni.

• Il vecchio metodo (QAOA): Ogni volta che dovevi costruire qualcosa, il robot usava esattamente lo stesso schema di blocchi, indipendentemente dal fatto che il puzzle fosse facile o difficile. Era come se dovessi costruire una casetta e un grattacielo usando lo stesso identico numero di mattoni e lo stesso ordine.
• Il risultato: Se il puzzle era difficile, il robot finiva per usare un numero enorme di mattoni (porte logiche), rendendo la costruzione lenta, costosa e piena di errori (rumore).

La Soluzione: I Robot "Adattivi"

Gli autori di questo studio hanno provato a insegnare ai robot a essere più flessibili. Invece di seguire un manuale fisso, questi nuovi robot (chiamati Algoritmi Variational Quantistici Adattivi) possono:

1. Guardare il puzzle.
2. Decidere quali mattoni servono davvero.
3. Aggiungerne di nuovi o toglierne di inutili mentre lavorano.
4. Ottimizzare la forma del puzzle man mano che procede.

L'obiettivo era capire: "Vale la pena usare robot che si adattano, o è meglio restare con il vecchio metodo rigido?"

I Tre "Allenatori" del Robot

Per fare questa prova, gli scienziati hanno messo a confronto tre diversi "allenatori" (algoritmi) che guidano il robot, più un vecchio metodo fisso:

1. L'Allenatore "Evolutivo" (EVQE): Funziona come l'evoluzione biologica. Immagina di avere una popolazione di robot che costruiscono il puzzle in modo diverso. Quelli che fanno un lavoro migliore "sopravvivono" e si riproducono, mentre quelli che falliscono vengono eliminati. Nel tempo, la popolazione impara a costruire circuiti sempre più efficienti.
2. L'Allenatore "Intelligente" (VAns): È come un architetto che sa semplificare. Parte con un progetto base, poi aggiunge pezzi a caso per vedere se migliorano il risultato. Ma la sua magia è che, ogni tanto, guarda il progetto e dice: "Ehi, questi due mattoni qui fanno la stessa cosa, togliamoli!". Usa regole matematiche per rendere il circuito più corto e pulito.
3. L'Allenatore "Casuale" (RA-VQE): È il giocatore d'azzardo. Aggiunge mattoni a caso, senza una strategia precisa, solo per vedere se per fortuna si trova una soluzione migliore. Serve come "punto di riferimento" per vedere se gli altri due sono davvero bravi o se è solo fortuna.
4. Il Vecchio Metodo (QAOA): Il costruttore rigido che usa sempre lo stesso schema.

L'Esperimento: La Gara

Gli scienziati hanno fatto gareggiare questi allenatori su tre tipi di problemi classici (come dividere un gruppo di persone in due squadre bilanciate, o coprire tutti i nodi di una rete). Hanno misurato:

• Quanto era buona la soluzione? (Il punteggio finale).
• Quanti mattoni (porte) ha usato? (La complessità).
• Quanto tempo ha impiegato? (La velocità).

I Risultati: Cosa è Emerso?

Ecco le scoperte principali, spiegate con metafore:

1. La Qualità è Uguale per Tutti:
   Tutti i metodi, sia quelli rigidi che quelli adattivi, sono riusciti a trovare soluzioni quasi perfette (punteggio vicino a 100%). Quindi, in termini di "risultato finale", non c'è una grande differenza.

2. La Differenza è nel "Peso" del Circuito:
   Qui sta il trucco. Il vecchio metodo rigido (QAOA) ha usato un numero enorme di mattoni (porte logiche), specialmente per i problemi grandi. È come se avesse costruito un grattacielo usando 10.000 mattoni, mentre gli allenatori adattivi ne hanno usati solo 10 o 20.

   • Perché è importante? I computer quantistici attuali sono fragili (rumorosi). Più mattoni usi, più è probabile che qualcosa si rompa o che il calcolo impieghi troppo tempo. I circuiti "leggeri" degli adattivi sono molto più sicuri e veloci.

3. Il Vincitore è l'Architetto (VAns):
   L'algoritmo VAns è stato il migliore in assoluto. È riuscito a trovare soluzioni eccellenti usando il minor numero possibile di mattoni. In alcuni casi, ha addirittura eliminato completamente i mattoni più complessi (le porte "CNOT"), rendendo il circuito quasi perfetto e brevissimo.

4. Il Ruolo della "Fortuna" e della "Strategia":
   Anche l'allenatore casuale (RA-VQE) ha fatto un ottimo lavoro, trovando circuiti brevi. Questo suggerisce che, a volte, non serve una strategia super-complessa: basta cercare bene e fermarsi quando si trova qualcosa di semplice. Tuttavia, l'architetto (VAns) è stato più costante e veloce.

La Conclusione in Pillole

Questo studio ci dice che non serve avere un computer quantistico gigante e perfetto per risolvere problemi complessi.
Basta usare algoritmi intelligenti che sappiano semplificare il lavoro.

• I vecchi metodi sono come un camioncino che porta tutto, anche ciò che non serve: lento e ingombrante.
• I nuovi metodi adattivi (soprattutto VAns) sono come un bici da corsa: leggeri, veloci e perfetti per la strada di oggi (i computer quantistici attuali).

In sintesi: La chiave del successo non è solo la potenza di calcolo, ma la capacità di essere snelli e adattarsi al problema specifico.

Sommario tecnico

1. Il Problema

Negli ultimi anni, gli Algoritmi Variazionali Quantistici (VQA) sono emersi come approccio promettente per risolvere problemi di ottimizzazione nell'era dei computer quantistici NISQ (Noisy Intermediate-Scale Quantum). Tuttavia, i VQA tradizionali soffrono di una limitazione significativa: dipendono da circuiti a struttura fissa (ansatz predefiniti). Questi circuiti potrebbero non essere ottimizzati per problemi specifici o per le configurazioni hardware disponibili, portando a circuiti troppo profondi, rumorosi o inefficienti.

Sebbene esistano diverse VQA Adattive che modificano dinamicamente la struttura del circuito aggiungendo o rimuovendo porte durante l'addestramento, manca nella letteratura un confronto sistematico tra i diversi metodi. Non è chiaro quale strategia adattiva (basata su euristiche, genetica o casuale) offra i migliori compromessi tra qualità della soluzione, complessità del circuito e tempo computazionale.

2. Metodologia

Gli autori hanno condotto un benchmark rigoroso applicando quattro algoritmi a istanze di problemi QUBO (Quadratic Unconstrained Binary Optimization), convertiti in problemi di ricerca dello stato fondamentale di un operatore Hamiltoniano.

Algoritmi Confrontati:

1. EVQE (Evolutionary Variational Quantum Eigensolver): Un algoritmo genetico che evolve una popolazione di circuiti. Utilizza operazioni di inserimento e rimozione di porte, ottimizzando i parametri solo dell'ultimo gene aggiunto. Evita il "crossover" (scambio di geni) perché la fusione di circuiti entangled non garantisce un discendente valido senza un riosottimizzazione completa.
2. VAns (Variable Ansatz): Un approccio euristico che parte da uno strato iniziale (Separable o Hardware Efficient) e aggiunge blocchi di porte (che compilano all'identità) in modo casuale. Successivamente, applica regole di semplificazione (algebriche e basate sui costi) per rimuovere porte ridondanti o inutili, mirando a circuiti più superficiali.
3. RA-VQE (Random Adapt-VQE): Una nuova baseline introdotta dagli autori. Costruisce il circuito aggiungendo porte casuali da un pool e ottimizzando tutti i parametri dopo ogni aggiunta, senza utilizzare euristiche specifiche per la struttura.
4. QAOA (Quantum Approximate Optimization Algorithm): L'algoritmo di riferimento a struttura fissa, utilizzato come termine di paragone per valutare il vantaggio degli approcci adattivi.

Protocollo Sperimentale:

• Istanze di Problema: MaxCut (su grafi Erdős-Rényi e a stella), Minimum Vertex Cover e Number Partitioning.
• Dimensioni: Variabili $N = 4, 8, 12, 15$.
• Ottimizzazione: Utilizzo dell'ottimizzatore classico COBYLA (senza gradiente) per i parametri del circuito.
• Budget Computazionale: Ogni algoritmo ha un budget massimo di $10^4$ valutazioni dell'aspettazione del circuito. Per QAOA, tutto il budget è dedicato all'ottimizzazione dei parametri (poiché la struttura è fissa), mentre per gli adattivi è diviso tra ricerca della struttura e ottimizzazione dei parametri.
• Tuning degli Iperparametri: È stata utilizzata un'ottimizzazione Bayesiana per selezionare i migliori iperparametri per ogni algoritmo e dimensione del problema, garantendo un confronto equo.

3. Contributi Chiave

• Primo Benchmark Comparativo: Il lavoro fornisce il primo confronto sistematico tra diverse VQA adattive (genetiche, euristica, casuale) e un metodo a struttura fissa (QAOA) su problemi QUBO.
• Introduzione di RA-VQE: Propone una baseline casuale per isolare l'effetto delle euristiche complesse rispetto alla semplice esplorazione casuale dello spazio delle strutture.
• Analisi Multidimensionale: Valuta le performance non solo sulla qualità della soluzione (rapporto di approssimazione), ma anche sul numero di porte (in particolare porte CNOT), sulla profondità del circuito e sui tempi di esecuzione.
• Impatto degli Iperparametri: Dimostra come la scelta degli iperparametri sia critica e come un tuning inadeguato possa degradare drasticamente le prestazioni.

4. Risultati Principali

I risultati sono stati ottenuti tramite simulatore di vettore di stato (IBM Qiskit) in scenari privi di rumore.

• Qualità della Soluzione (Rapporto di Approssimazione):

  • Tutti gli algoritmi (adattivi e QAOA) raggiungono rapporti di approssimazione molto vicini a 1, indicando che tutti sono in grado di trovare soluzioni di alta qualità.
  • Non vi è un vantaggio significativo in termini di precisione della soluzione tra gli algoritmi adattivi e QAOA.

• Efficienza del Circuito (Porte e CNOT):

  • VAns si distingue nettamente: produce circuiti con il minor numero di porte e CNOT (spesso zero CNOT per istanze piccole) e profondità estremamente ridotta (spesso profondità 1).
  • QAOA richiede un numero elevato di porte e CNOT, che cresce drasticamente con la dimensione del problema e la densità del grafo.
  • EVQE e RA-VQE si collocano in una posizione intermedia, ma RA-VQE dimostra che anche un approccio puramente casuale può trovare circuiti brevi ed efficienti.

• Tempi Computazionali:

  • VAns è quasi sempre il più veloce per istanze grandi ($N=12, 15$), grazie alla brevità dei circuiti generati che richiedono meno tempo di esecuzione e ottimizzazione.
  • QAOA ha tempi di esecuzione molto variabili e spesso più lunghi, specialmente su grafi densi, a causa della necessità di ottimizzare un gran numero di parametri in circuiti profondi.
  • EVQE e RA-VQE mostrano tempi di esecuzione elevati per istanze grandi, in parte a causa della complessità della ricerca della struttura e dell'ottimizzazione dei parametri.

• Ruolo degli Iperparametri:

  • L'ottimizzazione Bayesiana ha rivelato che configurazioni subottimali possono portare a perdite di performance significative (es. VAns con la peggiore configurazione ha ottenuto un loss di -37 contro -49 con la migliore).
  • Per QAOA, circuiti più profondi (p più alto) non sempre portano a migliori risultati in scenari privi di rumore, probabilmente perché l'ottimizzatore fatica a trovare l'ottimo globale con troppi parametri.

5. Significato e Conclusioni

Il paper conclude che, sebbene le VQA adattive non offrano un vantaggio immediato in termini di qualità della soluzione rispetto a QAOA in scenari ideali, offrono un vantaggio cruciale in termini di efficienza strutturale.

• VAns emerge come l'approccio più promettente, capace di bilanciare alta qualità della soluzione con circuiti estremamente compatti e superficiali. Questo è fondamentale per l'implementazione su hardware reale NISQ, dove il rumore e la profondità del circuito sono limitanti critici.
• Le strategie di semplificazione (come quelle usate da VAns) sono identificate come tecniche chiave che potrebbero essere trasferite ad altri algoritmi.
• L'approccio casuale (RA-VQE) dimostra che la ricerca della struttura non richiede necessariamente euristiche complesse per ottenere circuiti brevi, suggerendo che la semplicità è spesso un fattore determinante per il successo.

In sintesi, il lavoro sottolinea che la valutazione degli algoritmi quantistici deve considerare non solo l'accuratezza della soluzione, ma anche la complessità del circuito (numero di porte, profondità) e la flessibilità di adattarsi all'hardware specifico, dimensioni in cui le VQA adattive, e in particolare VAns, eccellono rispetto ai metodi a struttura fissa.