Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)

Questo documento dimostra che parallelizzare il Framework di Ottimizzazione a Decomposizione Auto Hamiltoniana (HADOF) su singoli e multipli processori quantistici IBM riduce significativamente il tempo reale necessario per risolvere problemi di ottimizzazione combinatoria su larga scala, inclusi casi reali di assemblaggio genomico, mantenendo al contempo la qualità della soluzione e avanzando verso il calcolo quantistico ad alte prestazioni.

L'essenziale

Immagina di stare cercando di risolvere un gigantesco, incredibilmente complesso puzzle. Non si tratta di un puzzle qualsiasi; è un "Puzzle Quantistico" che rappresenta un problema del mondo reale, come stabilire l'ordine corretto delle catene di DNA per assemblare un genoma.

Il problema è che il puzzle è troppo grande perché qualsiasi singola persona (o un singolo computer quantistico) possa tenerlo in mano. I pezzi sono troppo numerosi e il "rumore" nella stanza (errori hardware) rende difficile vedere l'immagine chiaramente. Se cerchi di forzare l'intero puzzle su un piccolo tavolo, non ci starà e probabilmente commetterai errori.

Questo articolo introduce una nuova strategia chiamata HADOF (Hamiltonian Auto Decomposition Optimisation Framework) per risolvere questo problema. Ecco come funziona, utilizzando semplici analogie:

1. Il Problema: Il Puzzle "Troppo Grande per Essere Tenuto"

I computer quantistici attuali sono come piccoli e rumorosi banchi di lavoro. Possono contenere solo pochi pezzi del puzzle alla volta. Se cerchi di risolvere un problema enorme (come un genoma con migliaia di frammenti di DNA) tutto in una volta su uno di questi banchi di lavoro, il computer viene sopraffatto, i pezzi vengono mescolati dal "rumore" e la soluzione fallisce.

2. La Soluzione: Spezzarlo in "Mini-Puzzle"

Invece di cercare di risolvere il puzzle gigante in un'unica soluzione, HADOF agisce come un maestro organizzatore. Scompone il puzzle massiccio in centinaia di minuscoli e gestibili "mini-puzzle" (sottoproblemi).

• Il Trucco Magico: Non si limita a tagliare il puzzle a caso. Utilizza un sistema intelligente per osservare i pezzi che hai già posizionato e usa quelle informazioni per aiutare a risolvere il prossimo mini-puzzle.
• L'Iterazione: Risolve un mini-puzzle, impara da esso, aggiorna la sua comprensione dell'immagine complessiva e poi risolve il successivo. Ripete questo processo finché l'intera immagine non è chiara.

3. La Nuova Svolta: La "Catena di Montaggio" (Parallelizzazione)

In precedenza, questo metodo funzionava come un singolo lavoratore su una catena di montaggio: risolve il mini-puzzle n. 1, poi il n. 2, poi il n. 3. Questo richiede molto tempo.

Gli autori di questo articolo hanno aggiornato il sistema per farlo funzionare come una folla di fabbrica con multiple catene di montaggio.

• Singolo Lavoratore vs. Squadra: Invece di una sola persona che risolve i mini-puzzle uno alla volta, hanno utilizzato una squadra di lavoratori (multipli Computer Quantistici, o QPU) per risolvere diversi mini-puzzle esattamente nello stesso momento.
• Il Risultato: Hanno scoperto che utilizzando una squadra di quattro computer quantistici, potevano completare il lavoro 3 o 4 volte più velocemente rispetto all'uso di un solo computer. Anche utilizzando un solo computer ma organizzando il lavoro in parallelo, diventava 3 volte più veloce.

4. Il Test del Mondo Reale: Riassemblare una "Storia" di DNA

Per dimostrare che questo funziona nel mondo reale, il team lo ha testato su un problema biologico specifico: l'Assemblaggio del Genoma.

• L'Analogia: Immagina di aver sminuzzato un libro in migliaia di striscioline di carta minuscole (letture del DNA). Il tuo compito è incollarle di nuovo insieme nell'ordine giusto per leggere la storia.
• Il Test: Hanno preso un vero set di dati biologici (un virus chiamato $\phi$X174) e hanno tentato di riassemblarlo utilizzando il loro nuovo "squadra di computer quantistici".
• L'Esito:
  • Velocità: L'approccio parallelo è stato molto più veloce nel ottenere un risultato.
  • Qualità: Sebbene i computer quantistici rumorosi non abbiano ottenuto un punteggio perfetto del 100% (a causa del "rumore" hardware), hanno comunque trovato soluzioni molto buone. In effetti, oltre il 50% delle soluzioni che hanno generato era corretto abbastanza da poter essere corretto nella risposta perfetta utilizzando strumenti standard di post-elaborazione.
  • Confronto: Quando hanno tentato di risolvere l'intero puzzle del DNA su un singolo computer quantistico senza scomporlo, il computer non è riuscito a trovare una buona soluzione. Il metodo "spezzalo in pezzi" (HADOF) ha avuto successo laddove il metodo "tutto in una volta" ha fallito.

5. Il Quadro Generale: "Quantistico ad Alte Prestazioni" (HPQ)

Gli autori definiscono questo approccio come calcolo Quantistico ad Alte Prestazioni (HPQ).

• Pensala come la differenza tra una singola persona che cerca di spostare una montagna di sabbia con un cucchiaino rispetto a una flotta di camion che lavora insieme.
• L'articolo sostiene che per rendere i computer quantistici davvero utili per i grandi problemi, non possiamo semplicemente aspettare che diventino più grandi e più silenziosi. Dobbiamo cambiare come li usiamo: spezzando i problemi in piccoli pezzi e risolvendoli in parallelo su molte macchine.

Riepilogo delle Affermazioni

• Velocità: Utilizzare multipli computer quantistici in parallelo rende la risoluzione di questi problemi 3–4 volte più veloce.
• Scalabilità: Questo metodo ci permette di risolvere problemi (come 500 variabili) che attualmente sono troppo grandi per essere gestiti da un singolo computer quantistico.
• Precisione: Anche con hardware rumoroso e imperfetto, questo metodo trova soluzioni migliori rispetto al tentativo di risolvere l'intero problema in una volta sola.
• Applicazione Reale: Ha dimostrato con successo questo su un compito reale di assemblaggio del genoma, mostrando che non è solo una teoria ma uno strumento funzionante.

In sintesi, l'articolo dice: "Non cercare di mangiare l'intero elefante in un solo boccone. Spezzalo in piccoli pezzi e fai in modo che una squadra di computer quantistici li mangi tutti contemporaneamente. È più veloce e funziona meglio."

Sommario tecnico

1. Enunciato del Problema

L'applicazione pratica dell'ottimizzazione quantistica per problemi combinatori (formulati come Quadratic Unconstrained Binary Optimization, o QUBO) è attualmente ostacolata dai limiti dei dispositivi Quantum a Scala Intermedia e Rumorosi (NISQ). I vincoli chiave includono:

• Numero Limitato di Qubit: L'hardware attuale non può ospitare grandi problemi QUBO che richiedono centinaia di variabili.
• Rumore dell'Hardware: L'accumulo di rumore nei circuiti profondi degrada la qualità della soluzione.
• Scalabilità: I metodi di decomposizione esistenti (come HADOF) sono prevalentemente sequenziali, non riuscendo a sfruttare il parallelismo disponibile nelle architetture quantistiche distribuite o nelle risorse di High Performance Computing (HPC).
• Limiti di Simulazione: Simulare circuiti quantistici su larga scala in modo classico è computazionalmente costoso e richiede molta memoria.

Il documento affronta queste problematiche estendendo il Hamiltonian Auto Decomposition Optimisation Framework (HADOF) per supportare l'esecuzione parallela su singole e multiple Quantum Processing Unit (QPU), con l'obiettivo di realizzare il calcolo quantistico ad alte prestazioni (HPQ).

2. Metodologia

Framework Principale: HADOF

HADOF scompone un Hamiltoniano QUBO globale in sotto-Hamiltoniani più piccoli e gestibili, risolvibili in modo iterativo.

1. Decomposizione: Il problema globale viene suddiviso in sottoproblemi (sottoinsiemi di variabili).
2. Risoluzione Iterativa: Ogni sottoproblema viene risolto utilizzando un ottimizzatore quantistico (QAOA).
3. Integrazione del Contesto: I valori attesi ($E[x_i]$) delle variabili provenienti dai sottoproblemi risolti vengono utilizzati per approssimare il contesto per i sottoproblemi successivi.
4. Aggregazione: Le soluzioni vengono ricomposte per formare una soluzione globale.

Estensione Parallela

Gli autori introducono una versione parallelizzata di HADOF che differisce dalla baseline sequenziale in due modi chiave:

• Generazione Indipendente: In ogni iterazione, tutti i sotto-Hamiltoniani vengono generati simultaneamente utilizzando i valori attesi dell'iterazione precedente (invece di aggiornare i valori in modo sequenziale all'interno dell'iterazione corrente).
• Esecuzione Asincrona: I sottocircuiti vengono risolti in concorrenza. Questo permette:
  • Parallelismo Intra-QPU: Esecuzione di più job su una singola QPU (sfruttando lo scheduler).
  • Parallelismo Inter-QPU: Distribuzione dei job su più QPU distinte (ad esempio, IBM Kingston, Pittsburgh, Fez, Marrakesh).

Dettagli di Implementazione

• Ottimizzatore: Utilizza un approccio QAOA digitalizzato con Parametrizzazione di Annealing Trotterizzato per evitare loop di ottimizzazione classica per i parametri $\beta$ e $\gamma$.
• Profondità del Circuito: I circuiti sono costruiti strato per strato (fino a 5 strati). In ogni iterazione, viene aggiunto uno strato a tutti i sottocircuiti.
• Dimensione del Sottoproblema: Fissata a 5 qubit ($k=5$) per mantenere un'alta fedeltà sull'hardware attuale.
• Applicazione Target: Assemblaggio del Genoma, modellato come un Problema del Commesso Viaggiatore (TSP) su un grafo di sovrapposizione. Il problema è codificato in un QUBO dove l'obiettivo è trovare il percorso hamiltoniano.

3. Contributi Chiave

1. Prima Implementazione HADOF su Dispositivo Reale: Lo studio sposta HADOF dalla simulazione teorica all'esecuzione su QPU IBM reali (Kingston, Pittsburgh, Fez, Marrakesh).
2. Strategia di Parallelizzazione: Dimostra un framework per l'esecuzione concorrente di sottoproblemi decomposti, ottenendo significativi accelerazioni nel tempo reale (wall-clock time) senza compromettere la qualità della soluzione.
3. Validazione del Paradigma HPQ: Posiziona HADOF come un percorso praticabile verso il calcolo quantistico ad alte prestazioni, integrando la decomposizione algoritmica con il parallelismo a livello di sistema.
4. Applicazione nel Mondo Reale: Applica con successo il framework a un problema di assemblaggio del genoma (batteriofago ϕX174), dimostrandone l'utilità nella biologia computazionale.
5. Benchmarking: Fornisce un confronto completo tra HADOF Sequenziale, HADOF Parallelo (Singola e Multi-QPU), QAOA Standard a Circuito Completo e Ricottura Simulata Classica.

4. Risultati Chiave

Velocità ed Efficienza

• Tempo Wall Clock:
  • Parallelo Multi-QPU: Ha ottenuto una riduzione di 3–4 volte nel tempo wall clock rispetto all'esecuzione sequenziale su hardware reale.
  • Parallelo Singola-QPU: Ha ottenuto fino a un acceleramento di 3 volte anche su un singolo dispositivo grazie all'orchestrazione efficiente dei job.
  • Simulazione: Ha previsto un acceleramento >5 volte nelle modalità di simulazione parallela.
• Utilizzo QPU: Sebbene il tempo totale di utilizzo della QPU rimanga proporzionale al numero di circuiti, il makespan (tempo totale per la soluzione) è drasticamente ridotto, rendendo l'approccio pratico per applicazioni sensibili al tempo.

Accuratezza e Robustezza

• vs QAOA Standard: HADOF supera significativamente il QAOA a circuito completo su hardware reale.
  • L'accuratezza del QAOA standard è scesa a quasi zero (ad esempio, 0.02) per problemi a 50 variabili su hardware rumoroso a causa dell'accumulo di rumore.
  • HADOF ha mantenuto un'accuratezza >0.80 su hardware reale per dimensioni simili.
• Resilienza al Rumore: La decomposizione limita la profondità del circuito, prevenendo il degrado esponenziale dell'accuratezza osservato nei circuiti monolitici.
• Caso di Studio: Assemblaggio del Genoma:
  • Simulazione Ideale: Sia HADOF sequenziale che parallelo hanno raggiunto il 100% di accuratezza migliore (corrispondente alla Ricottura Simulata).
  • Hardware Reale: L'accuratezza migliore è rimasta competitiva (0.88–0.91), sebbene la frequenza di trovare lo stato fondamentale esatto sia scesa a zero a causa del rumore. Tuttavia, >52% delle soluzioni campionate potevano essere post-elaborate per recuperare la sequenza corretta utilizzando strumenti bioinformatici standard (GFAtools).

Scalabilità

• HADOF ha risolto con successo problemi QUBO con fino a 500 variabili in simulazione e 300 variabili su hardware reale utilizzando circuiti da soli 5 qubit.
• Il QAOA standard a circuito completo è limitato a ~50 variabili sullo stesso hardware a causa dei vincoli di connettività e embedding.

5. Significato e Conclusione

Questa ricerca dimostra che decomposizione e parallelismo non sono semplici soluzioni di ripiego per i limiti attuali dell'hardware, ma sono abilitatori fondamentali di un vantaggio quantistico pratico.

• Scalabilità: HADOF aggira i limiti fisici dei qubit dei dispositivi attuali, permettendo la risoluzione di problemi molto più grandi di quanto l'hardware possa supportare nativamente.
• Allineamento HPQ: Il framework si allinea con il paradigma emergente del calcolo quantistico ad alte prestazioni, mostrando che le architetture quantistiche distribuite possono fornire guadagni di prestazioni sostanziali.
• Fattibilità Pratica: Applicando con successo il metodo all'assemblaggio del genoma, il documento dimostra che l'ottimizzazione quantistica può essere integrata in pipeline scientifiche reali, a condizione che il rumore sia gestito attraverso strategie di decomposizione ed esecuzione parallela.

Gli autori concludono che il lavoro futuro dovrebbe concentrarsi su strategie di decomposizione adattive, tecniche di mitigazione degli errori e sull'integrazione di HADOF nelle pipeline standard di assemblaggio del genoma con dati di sequenziamento reali.