Riepilogo Tecnico: Scalabilità del Mappaggio e dell'Instradamento dei Qubit con Astrazione del Grafo di Posizione e Memorizzazione

Enunciato del Problema

Il mappaggio e l'instradamento scalabili dei qubit rimangono colli di bottiglia critici nella compilazione quantistica, in particolare per le architetture TI-QCCD (Trapped-Ion Quantum Charge-Coupled Device). A differenza dei sistemi a superconduttori, dove l'instradamento è modellato tramite operazioni SWAP su un grafo di accoppiamento statico, il TI-QCCD richiede lo spostamento fisico degli ioni attraverso segmenti e giunzioni. Questo processo è vincolato dalla legalità dei movimenti, dai limiti di capacità delle trappole e dalla congestione (dove le posizioni intermedie sono occupate).

I metodi euristici esistenti, come SABRE, si basano su astrazioni come i Grafi di Accoppiamento che sono insufficienti per il TI-QCCD perché non possono esprimere i vincoli complessi del trasporto fisico, dell'occupazione intermedia e del blocco dei percorsi. Sebbene un lavoro precedente avesse introdotto l'astrazione del Grafo di Posizione per unificare le posizioni eseguibili, i percorsi di movimento e i vincoli di instradamento, la sua implementazione iniziale soffriva di gravi problemi di scalabilità. Ad esempio, la compilazione di un circuito a 128 qubit su un dispositivo a 180 ioni poteva richiedere un giorno a causa di calcoli ridondanti durante la ricerca euristica e la risoluzione della congestione.

Metodologia

Il documento propone un framework di compilazione che potenzia l'astrazione del Grafo di Posizione con strategie di caching e memorizzazione per eliminare i calcoli ridondanti senza alterare le decisioni di instradamento.

1. Astrazione del Grafo di Posizione

Il framework utilizza il Grafo di Posizione ($G_p$), un grafo etichettato in cui:

• I Vertici rappresentano posizioni fisiche occupabili (trappole, regioni di trasporto intermedie).
• Gli Archi rappresentano transizioni valide (swap all'interno di una trappola, unione/divisione tra trappola e trasporto, o movimento all'interno del trasporto).
• Le Etichette distinguono i tipi di operazione (swap, unione/divisione, movimento).
  Questa astrazione generalizza il Grafo di Accoppiamento (utilizzato per i sistemi a superconduttori) per supportare la topologia più ricca del TI-QCCD.

2. Caching a Livello di Architettura

Per ridurre l'overhead, gli autori pre-calcolano e memorizzano in cache quantità dipendenti dall'architettura che rimangono statiche durante una sessione di compilazione:

• Percorsi più brevi tra tutte le coppie e matrici delle distanze.
• Sottografi eseguibili derivati dalle etichette degli archi.
• Profilo di blocco dei percorsi: Per qualsiasi movimento da sorgente a destinazione, una lista memorizzata di posizioni intermedie che potrebbero causare blocchi, insieme a penalità fisse per la loro risoluzione.

3. LightSHAW: Risoluzione della Congestione con Memorizzazione

Il contributo principale è LightSHAW, una variante con caching dell'euristica SHAW (SHuttling-AWare). SHAW risolve la congestione ricorsivamente quando uno ione in movimento è bloccato da una posizione occupata. LightSHAW ottimizza questo processo tramite una cache a due livelli:

• Cache Locale dell'Insieme di Punteggi: Memorizza l'insieme di posizioni vicine da ispezionare per un dato movimento di sgombro candidato, evitando la ripetuta traversata del grafo per definire il vicinato di ricerca.
• Memorizzazione della Congestione Chiavata per Configurazione: Memorizza il punteggio di congestione basandosi su una "firma di occupazione locale" ($\sigma$). La chiave è $(p, t, b, d, \sigma)$, dove $p$ è la posizione candidata, $t$ è la destinazione, $b$ è il blocco, $d$ è la profondità di ricerca e $\sigma$ rappresenta l'occupazione dell'insieme di punteggi locale. Ciò permette al sistema di riutilizzare i punteggi per pattern di congestione locale ripetuti senza scansionare nuovamente l'intero dispositivo.

4. Potatura della Selezione delle Trappole

Per ottimizzare la selezione delle trappole target per le porte multi-qubit, gli autori implementano una strategia di potatura basata su un limite inferiore. Calcolano un limite inferiore ottimistico sul costo di instradamento per ogni trappola (ignorando la congestione e i requisiti distinti delle slot). Le trappole sono valutate in ordine crescente di questo limite; la valutazione esatta si interrompe non appena il limite inferiore del prossimo candidato supera il miglior punteggio esatto trovato finora.

5. Validazione su Architetture a Superconduttori

Per garantire che il Grafo di Posizione non imponga un overhead inutile su architetture più semplici, gli autori hanno istanziato LightSABRE (una variante di SABRE) utilizzando sia un backend tradizionale basato su Grafo di Accoppiamento sia un backend basato su Grafo di Posizione. Entrambe le implementazioni sono state configurate per prendere decisioni di instradamento identiche, isolando il costo dell'astrazione stessa.

Contributi Chiave

1. Rimozione dei Calcoli Ridondanti: Identificazione e caching dei percorsi MOVE più brevi, delle distanze dei tempi di viaggio e delle informazioni sui percorsi relative ai blocchi in SHAW.
2. Algoritmo LightSHAW: Introduzione di una procedura di risoluzione della congestione con memorizzazione che riutilizza informazioni dipendenti dall'architettura (percorsi di movimento, regioni locali di sgombro) e punteggi di occupazione locale, riducendo significativamente il lavoro ripetuto durante la pulizia ricorsiva dei blocchi.
3. Analisi dell'Overhead dell'Astrazione: Dimostrazione che il Grafo di Posizione può sostituire il Grafo di Accoppiamento per l'instradamento LightSABRE con un overhead di runtime trascurabile, provando che modelli architetturali più ricchi non compromettono intrinsecamente la velocità di compilazione.
4. Framework Open-Source: Fornitura di un'implementazione che supporta flussi di lavoro sia per superconduttori che per TI-QCCD, facilitando la sperimentazione su architetture quantistiche eterogenee.

Risultati Sperimentali

Gli autori hanno valutato il framework utilizzando benchmark inclusi circuiti QAOA, QFT e di simulazione Hamiltoniana (TFIM, TFXY) che variano da 16 a 512 qubit.

• Scalabilità del Tempo di Compilazione: LightSHAW supera significativamente l'SHAW originale e il simulatore QCCDSim all'avanguardia in termini di scalabilità.
  • SHAW: Scala come $O(x^{3.91})$.
  • QCCDSim: Scala come $O(x^{3.04})$.
  • LightSHAW: Scala come $O(x^{1.72})$.
  • Sebbene LightSHAW abbia un overhead maggiore per circuiti molto piccoli rispetto a QCCDSim, eguaglia o supera le prestazioni di QCCDSim su circuiti più grandi (ad esempio, architetture a 180 ioni) e scala in modo molto più favorevole.
• Tempo di Operazione (Qualità): LightSHAW produce schedulazioni con un tempo totale di operazione (esecuzione delle porte + spostamento) significativamente inferiore rispetto a QCCDSim. Ad esempio, su un circuito QAOA a 512 qubit, LightSHAW ha raggiunto un rapporto di tempo di operazione di 0,171 rispetto a QCCDSim, indicando una riduzione di circa 6 volte nel tempo di esecuzione.
• Robustezza: In scenari rigorosi con vincoli di risorse (alta utilizzazione degli ioni per trappola), QCCDSim ha spesso fallito nel produrre compilazioni valide (denotate come 'X' nei risultati), mentre LightSHAW ha completato con successo tutte le istanze.
• Compatibilità con Superconduttori: Quando applicato all'instradamento a superconduttori (LightSABRE), il backend del Grafo di Posizione ha eguagliato il runtime del backend tradizionale del Grafo di Accoppiamento, confermando che l'astrazione non introduce penalità significative per architetture più semplici.

Significato

Il documento sostiene che l'astrazione del Grafo di Posizione fornisce un percorso pratico ed efficace verso il mappaggio e l'instradamento scalabili dei qubit su architetture quantistiche eterogenee. Combinando una rappresentazione consapevole dell'architettura con una valutazione euristica memorizzata, il framework risolve il collo di bottiglia della scalabilità della compilazione TI-QCCD senza sacrificare le prestazioni sui sistemi a superconduttori. I risultati suggeriscono che l'infrastruttura dei compilatori può andare oltre i modelli minimi di adiacenza per supportare vincoli fisici complessi (come lo spostamento) mantenendo l'efficienza richiesta per la compilazione quantistica su larga scala. Il lavoro stabilisce che una rappresentazione unificata può servire sia architetture basate su SWAP che basate su spostamento, consentendo a un singolo framework di gestire vincoli hardware diversi.