No Tile Left Behind: Multiprogramming for Surface-Code Architectures

Questo documento introduce un framework formale per architetture di calcolo quantistico tolleranti ai guasti a multiprogrammazione che affronta i vincoli strutturali unici dei layout di circuiti basati su codici di superficie attraverso una pianificazione consapevole della gerarchia e una gestione dinamica delle risorse, ottenendo un aumento della velocità del sistema di 3,1 volte rispetto alle basi di riferimento esistenti.

L'essenziale

Immagina un futuro in cui i computer quantistici sono così avanzati da poter risolvere problemi impossibili per i supercomputer di oggi. Per realizzare ciò, queste macchine devono essere incredibilmente affidabili, utilizzando un sistema chiamato Computazione Quantistica Tollerante ai Guasti (FTQC).

Tuttavia, costruire un computer quantistico è come costruire una città enorme e altamente organizzata. Non puoi semplicemente gettare persone casuali (dati) nelle strade; hanno bisogno di quartieri specifici, strade specifiche e linee di approvvigionamento specifiche per funzionare senza commettere errori.

Questo articolo, intitolato "No Tile Left Behind", affronta un problema specifico: Come possiamo eseguire più lavori diversi contemporaneamente in questa città quantistica senza causare ingorghi o rimanere senza spazio?

Ecco la spiegazione utilizzando analogie semplici:

1. La Città Quantistica: Codici di Superficie

Immagina il layout del computer quantistico come una gigantesca griglia di piastrelle (come una pianta del pavimento).

• Piastrelle Dati: Queste sono le "case" dove risiede l'informazione effettiva (i qubit logici).
• Piastrelle Ancilla: Queste sono le "squadre di costruzione" o i "banchi di lavoro". Sono spazi temporanei utilizzati per verificare gli errori o spostare i dati.
• Porti degli Stati Magici: Queste sono "fabbriche specializzate" che producono un ingrediente raro e di alta qualità (stati magici) necessario per eseguire calcoli complessi. Senza di esse, il computer non può eseguire certi calcoli matematici.

In passato (l'era "NISQ"), eseguire più lavori era come cercare di parcheggiare auto in un parcheggio vuoto. Le collocavi semplicemente dove riuscivi. Ma in questa nuova era "Tollerante ai Guasti", la città è strutturata. Non puoi parcheggiare ovunque; hai bisogno di un intero quartiere, di un banco di lavoro vicino e di una fabbrica nelle vicinanze. Se parcheggi un'auto male, potresti bloccare la strada per le successive tre auto.

2. Il Problema: L'Incubo del "Ripacking"

Gli autori spiegano che eseguire più lavori (multiprogrammazione) su questa griglia strutturata è molto più difficile di prima.

• Frammentazione: Se posizioni il Lavoro A in modo da lasciare un piccolo spazio inutile tra due grandi blocchi, il Lavoro B potrebbe aver bisogno di un grande blocco e non riuscire a inserirsi in quello spazio. Lo spazio è "frammentato".
• Carenza di Risorse: Se il Lavoro A si prende tutti i "banchi di lavoro" (ancilla) vicini, il Lavoro B potrebbe dover aspettare per sempre per completare il suo lavoro, anche se c'è spazio vuoto altrove.
• Il Collo di Bottiglia degli Stati Magici: Se ci sono solo poche "fabbriche" (porti degli stati magici) e tre lavori ne hanno bisogno contemporaneamente, due di essi devono attendere.

3. La Soluzione: Un Pianificatore Urbano Intelligente

Il team ha creato un nuovo "programmatore" (un pianificatore urbano intelligente) che gestisce questa griglia. Invece di semplicemente inserire i lavori, utilizza un insieme di regole per garantire che tutto si adatti perfettamente.

Come funziona il loro pianificatore:

• La Regola del "Cluster Compatto": Quando arriva un nuovo lavoro, il pianificatore non cerca solo qualsiasi spazio vuoto. Cerca un gruppo compatto e stretto di "case" proprio accanto alla "fabbrica" assegnata al lavoro. Costruisce il quartiere del lavoro come un cluster stretto ed efficiente in modo da non sprecare spazio.
• La Gerarchia dei "Banchi di Lavoro": Il pianificatore sa che alcuni banchi di lavoro sono più importanti di altri.
  • Banchi di Lavoro Core: Questi sono assegnati permanentemente a un lavoro.
  • Taccuini Primari: Questi sono banchi di lavoro vicini che il lavoro utilizza frequentemente.
  • Taccuini Secondari: Questi sono banchi di lavoro condivisi che il lavoro può prendere in prestito se necessario.
    Il pianificatore condivide dinamicamente queste risorse. Se un lavoro non sta utilizzando il suo banco di lavoro secondario, un altro lavoro può prenderlo in prestito, evitando tempi di inattività.
• L'Aggiornamento "Coltivazione": In una versione più avanzata del loro sistema, eliminano le "fabbriche" fisse. Invece, qualsiasi piastrella "banco di lavoro" vuota può temporaneamente trasformarsi in una fabbrica per produrre gli ingredienti necessari (stati magici) e poi tornare a essere un banco di lavoro una volta finito. È come avere una cucina mobile che si allestisce ovunque ci sia spazio, invece di costruire un ristorante permanente in un unico punto.

4. I Risultati: Più Veloce e Più Fluida

Gli autori hanno testato il loro sistema utilizzando simulazioni al computer con migliaia di lavori quantistici finti.

• Velocità: Il loro sistema ha eseguito i lavori 3,1 volte più velocemente rispetto all'esecuzione uno alla volta.
• Miglioramento: È stato circa 29% più veloce rispetto al metodo precedente migliore per gestire più lavori.
• Equità: Anche con molti lavori in esecuzione contemporaneamente, il "rallentamento" per qualsiasi singolo lavoro è stato molto piccolo (solo circa il 10% più lento rispetto a se fosse stato eseguito da solo).
• Efficienza Spaziale: Il loro metodo ha mantenuto la "città" molto meno frammentata, lasciando grandi pezzi utilizzabili di spazio disponibili per nuovi lavori, invece di un mucchio di piccoli spazi inutilizzabili.

Riassunto

In breve, questo articolo presenta un nuovo modo per gestire un computer quantistico costruito come una città strutturata. Utilizzando regole intelligenti per impacchettare i lavori in modo stretto, condividere le risorse dinamicamente e persino trasformare spazi vuoti in fabbriche temporanee, possono eseguire molti lavori complessi contemporaneamente in modo molto più efficiente rispetto a prima. Chiamano questo approccio "No Tile Left Behind" perché assicurano che ogni singolo pezzo della pianta del pavimento quantistico sia utilizzato efficacemente.

Sommario tecnico

1. Enunciato del Problema

Con il passaggio del calcolo quantistico dall'era NISQ (Noisy Intermediate-Scale Quantum) al Calcolo Quantistico Tollerante ai Guasti (FTQC), la sfida del multiprogrammazione (esecuzione concorrente di più carichi di lavoro) evolve significativamente.

• Il Cambiamento di Astrazione: Nel NISQ, la multiprogrammazione gestisce la topologia fisica dei qubit e il rumore. Nell'FTQC, specificamente nelle architetture a Codice Superficiale, l'astrazione si sposta sui qubit logici protetti dalla Correzione di Errori Quantistica (QEC).
• La Sfida Principale: L'hardware FTQC non è un pool piatto di qubit, ma un "layout" strutturato composto da:
  1. Piastrelle Dati: Patch logiche che memorizzano i qubit.
  2. Piastrelle Ancilla: Spazio di lavoro temporaneo per la chirurgia del reticolo (misurazione, instradamento).
  3. Risorse di Stato Magico: Fabbriche o porte dedicate per le porte non-Clifford (T).
• La Difficoltà: L'esecuzione concorrente deve gestire vincoli spaziotemporali. Un posizionamento inadeguato porta alla frammentazione del layout, alla carenza di risorse di stato magico e alla contesa per le piastrelle ancilla, degradando il throughput e la Qualità del Servizio (QoS). Gli scheduler NISQ esistenti sono insufficienti perché non tengono conto di questi layout logici strutturati e vincolati dalle risorse.

2. Metodologia

Gli autori propongono un framework formale e uno scheduler euristico per gestire questi vincoli.

A. Astrazione Hardware

Il layout del codice superficiale è modellato come un grafo non pesato e non diretto $G=(V, E)$, dove i vertici rappresentano le piastrelle (Dati, Ancilla, Porte di Stato Magico).

• Rappresentazione del Carico di Lavoro: Un carico di lavoro è un sottografo connesso contenente un insieme di piastrelle dati, un insieme di piastrelle ancilla (core) e una porta di stato magico.
• Classi di Risorse:
  • Ancilla Core: Fissate permanentemente al carico di lavoro.
  • Scratchpad Primario: Ancilla adiacenti al core, utilizzate per operazioni immediate.
  • Scratchpad Secondario: Pool elastico di ancilla condiviso.

B. Allocazione Statica (Baseline)

Per un batch di carichi di lavoro con risorse sufficienti, gli autori definiscono un Problema di Allocazione Statica per minimizzare l'impegno delle ancilla mantenendo la connettività.

• Algoritmo 1 (Partizionamento Compatto Greedy): Assegna le piastrelle dati ai carichi di lavoro partendo dal vertice dati più vicino a una porta di stato magico ed espandendo greedy il cluster verso il vertice dati non occupato più vicino. Questo garantisce compattezza spaziale e minimizza la frammentazione.
• Algoritmo 2 (Costruzione Incrementale del Core Radicato): Connette il cluster di dati assegnato alla porta di stato magico utilizzando il numero minimo di piastrelle ancilla (euristica dell'albero di Steiner), formando un sottografo residente connesso.

C. Scenari con Risorse Limitate e Scheduling Online

Il framework si estende a scenari in cui le risorse (Dati, Porte di Stato Magico o Ancilla) sono scarse e i carichi di lavoro arrivano online.

• Piastrelle Dati Limitate: Utilizza una politica di ammissione "best-fit". I carichi di lavoro sono prioritizzati in base alle dimensioni e a quanto bene si adattano alle regioni libere rimanenti per evitare la frammentazione.
• Porte di Stato Magico Limitate: Le porte sono trattate come servizi condivisi. Lo scheduler assegna dinamicamente le porte in base alla latenza di consegna ($T_{init} + T_{prep} + \text{distanza}$), utilizzando una priorità lessicografica per risolvere le contese.
• Piastrelle Ancilla Limitate: Introduce una politica di condivisione gerarchica.
  • Ancilla Core è strettamente fissata.
  • Scratchpad Primari/Secondari sono elastici.
  • Una Macchina a Stati (CODA $\to$ PARCHEGGIATO $\to$ PRONTO $\to$ ATTIVO) gestisce i carichi di lavoro. Se le risorse non sono disponibili, i carichi di lavoro vengono "parcheggiati" (rilasciando le ancilla core ma mantenendo i dati fissati) o ritardati in stati di attesa.

D. Architetture Abilitate alla Coltivazione

Il framework è generalizzato per supportare la Coltivazione di Stati Magici, dove gli stati magici sono generati su richiesta su piastrelle ancilla inattive invece che tramite fabbriche di distillazione fisse.

• Astrazione Dinamica: Rimuove le porte di stato magico fisse. Le piastrelle ancilla ciclan tra gli stati Coltivazione, Instradamento e Pronto.
• Arbitrazione: Lo scheduler riconquista dinamicamente le piastrelle di coltivazione per l'instradamento se necessario, dando priorità al movimento dei dati rispetto alla generazione di stati magici, per poi riprendere la coltivazione.

3. Contributi Chiave

1. Framework Formale: Ha definito la multiprogrammazione FTQC come un problema di posizionamento spaziotemporale multi-vincolato, catturando congiuntamente i vincoli di dati, ancilla e stato magico.
2. Algoritmi Euristic: Ha sviluppato l'Algoritmo 1 (partizionamento compatto dei dati) e l'Algoritmo 2 (costruzione del core ancilla minimale) per minimizzare lo spreco di risorse e la frammentazione.
3. Politiche Gerarchiche: Ha progettato politiche per scenari con risorse limitate (dati, porte, ancilla) e arrivi di job online, utilizzando un approccio a macchina a stati per l'arbitrazione delle risorse.
4. Integrazione della Coltivazione: Ha esteso il framework per supportare la generazione dinamica di stati magici, eliminando la necessità di fabbriche di distillazione fisse.

4. Risultati Sperimentali

Gli autori hanno valutato il framework utilizzando carichi di lavoro sintetici Clifford+T su un layout 20x12 (50% di densità dati).

• Miglioramento del Throughput:
  • Ha raggiunto un speedup di sistema normalizzato di 3,1× rispetto all'esecuzione sequenziale autonoma.
  • Ha superato lo stato dell'arte precedente (baseline ILP-C e Corner Greedy) di circa il 29%.
  • Ha superato le baseline casuali e naive di circa il 64% e il 43%, rispettivamente.
• Riduzione della Frammentazione: Il framework proposto ha mantenuto circa il 10% in più di spazio libero contiguo nel layout durante l'esecuzione di picco rispetto alle baseline, dimostrando la sua efficacia nel prevenire la frammentazione.
• Qualità del Servizio (QoS):
  • Il rallentamento medio (rapporto tra tempo di esecuzione condiviso e tempo autonomo) è stato mantenuto basso a circa 1,10×.
  • Il principale collo di bottiglia identificato è stata la contesa per le ancilla scratchpad secondarie sotto carichi pesanti.
• Benefici della Coltivazione:
  • Il passaggio ad architetture abilitate alla coltivazione ha aumentato il throughput di circa il 10% e ridotto il rallentamento di circa l'1%.
  • Risparmio di Risorse: Ha eliminato la necessità di fabbriche di distillazione fisse, risparmiando circa 173.000 qubit fisici (per un codice di distanza 23) rimuovendo l'impronta della fabbrica dedicata.

5. Significato

Questo documento affronta un divario critico nella roadmap verso il calcolo quantistico su larga scala. Man mano che l'hardware scala verso centinaia di qubit logici, la capacità di condividere risorse in modo efficiente è fondamentale.

• Impatto Architettonico: Si sposta oltre il semplice conteggio dei qubit verso una visione olistica della gestione del layout logico, riconoscendo che la frammentazione è il principale fattore che uccide le prestazioni nell'FTQC.
• Scalabilità: Le euristiche proposte sono computazionalmente efficienti e scalabili, rendendole fattibili per lo scheduling quantistico cloud in tempo reale.
• Preparazione al Futuro: Integrando la coltivazione di stati magici, il framework si allinea con le tendenze hardware emergenti che favoriscono l'uso dinamico delle risorse rispetto alle fabbriche statiche e pesanti a livello hardware, riducendo significativamente il sovraccarico di qubit fisici richiesto per la tolleranza ai guasti.

In sintesi, "No Tile Left Behind" fornisce il primo approccio completo e formalizzato alla multiprogrammazione nell'FTQC a codice superficiale, dimostrando che una gestione intelligente delle risorse spaziali e temporali può produrre guadagni di prestazioni sostanziali e risparmi di risorse per i futuri provider di cloud quantistico.