⚛️ quantum physics

MOSAIQC: Mixed-topology-aware Optimization for Scalable Approximate noise-Informed Quantum circuit Cutting

MosaiQC è un framework innovativo che impiega un warmstart ibrido con ottimizzazione di raffinamento e un risolutore approssimativo veloce per l'assegnazione quadratica per abilitare partizioni hardware a topologia mista e dimensione mista, migliorando significativamente la fedeltà locale e riducendo drasticamente i tempi di esecuzione e l'overhead di campionamento per il taglio scalabile di circuiti quantistici.

Autori originali: Koen Mesman, Yinglu Tang, Matthias Moller, Boyang Chen, Sebastian Feld

Pubblicato 2026-07-22

📖 4 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Koen Mesman, Yinglu Tang, Matthias Moller, Boyang Chen, Sebastian Feld

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di cercare di risolvere un enorme e impossibile puzzle, ma hai a disposizione solo un tavolino minuscolo su cui lavorare. Non riesci a far stare l'intera immagine sul tavolo tutto in una volta, quindi devi dividere il puzzle in blocchi più piccoli, risolvere ogni blocco sul tuo piccolo tavolo e poi cercare di incollarli insieme per vedere l'immagine finale. Questa è la lotta quotidiana degli scienziati che lavorano con i computer quantistici. Queste macchine sono incredibilmente potenti ma attualmente molto piccole e fragili; hanno troppo pochi "qubit" (i pezzi del puzzle) per gestire i grandi problemi che vorremmo far risolvere loro, e vengono facilmente disturbate dal rumore, come uno starnuto che rovina una delicata pila di carte.

Per aggirare questo problema, gli scienziati usano un trucco chiamato circuit cutting (taglio dei circuiti). È come prendere quel gigantesco puzzle, dividerlo in sezioni gestibili, risolvere ogni sezione su tavoli diversi (o persino su computer diversi) e poi usare una speciale ricetta matematica per riassemblare le risposte. Tuttavia, c'è un intoppo: ogni volta che tagli il puzzle, la ricetta per incollarlo di nuovo diventa esponenzialmente più difficile e richiede di scattare milioni di foto ai pezzi per ottenere l'immagine corretta. Se fai troppi tagli, lo sforzo per incollarli insieme diventa così enorme da vanificare lo scopo iniziale. La grande domanda è: dove esattamente dovremmo effettuare i tagli per mantenere i pezzi del puzzle abbastanza piccoli da essere risolti, ma senza fare così tanti tagli da rendere il processo di incollaggio infinito?

È qui che entra in gioco un nuovo framework chiamato MosaiQC. Immagina MosaiQC come un maestro del puzzle super intelligente e iper organizzato che non si limita a tagliare il puzzle in modo casuale. Invece, osserva la forma dei pezzi del puzzle, la dimensione dei tavoli disponibili e persino quanto ogni tavolo sia traballante (il "rumore"). Utilizza un mix astuto di strategie per trovare i punti di taglio perfetti. Per prima cosa, fa una supposizione rapida e approssimativa su dove tagliare (come un riscaldamento); poi affina questa supposizione testando piccoli movimenti, scambiando i pezzi tra loro per vedere se il puzzle si incastra meglio. Fondamentalmente, non gli interessa solo quanti tagli effettua; gli interessa anche dove finiscono i pezzi. Se un tavolo è traballante, MosaiQC cerca di mettere i pezzi più importanti e fragili sul tavolo più stabile per evitare errori.

Il documento mostra che questo nuovo metodo è un vero punto di svolta. Quando i ricercatori hanno testato MosaiQC rispetto ai metodi precedenti, hanno scoperto che era 2,88 volte più veloce nel capire dove tagliare. Ancora più importante, ha ridotto il numero di tagli necessari in media del 16,84%, il che sembra poco, ma in realtà significa che lo sforzo di "incollaggio" (l'overhead di campionamento) è diminuito di un fattore sbalorditivo di 5,38 × 10¹¹. È come passare dal dover scattare una foto a ogni singolo granello di sabbia su una spiaggia al dover scattare una sola foto dell'intera spiaggia in un colpo solo. Inoltre, prestando attenzione a quale hardware è più "rumoroso", MosaiQC ha migliorato l'accuratezza finale dei risultati di circa il 19,56% rispetto ai metodi standard.

Gli autori sottolineano con cautela che, sebbene MosaiQC renda la pianificazione dei tagli molto più veloce e migliore, il problema fondamentale di incollare i pezzi insieme richiede comunque molto sforzo se i tagli sono troppo numerosi. Tuttavia, trovando tagli migliori e posizionandoli sull'hardware più adatto, MosaiQC suggerisce che possiamo risolvere problemi quantistici molto più grandi rispetto a prima, senza rimanere bloccati in un collo di bottiglia della compilazione. Dimostra che un approccio intelligente e flessibile — che combina diversi tipi di tagli e si adatta a diverse dimensioni dell'hardware — può rendere l'impossibile un po' più possibile, aprendo la strada affinché i computer quantistici possano affrontare sfide del mondo reale anche prima di diventare enormi.

Sintesi Tecnica: MOSAIQC

Definizione del Problema

Gli attuali computer quantistici, particolarmente quelli nell'era NISQ (Noisy Intermediate-Scale Quantum), mancano delle risorse di qubit e della fedeltà necessarie per eseguire la maggior parte degli algoritmi quantistici pratici. Per aggirare questi limiti hardware, il "quantum circuit cutting" (o circuit knitting) è emerso come una tecnica per dividere grandi algoritmi in partizioni più piccole eseguibili sull'hardware disponibile. Tuttavia, questo approccio introduce un significativo overhead di campionamento che scala esponenzialmente con il numero di tagli richiesti per la ricostruzione esatta dello stato.

Gli attuali framework di ottimizzazione per determinare le posizioni dei tagli affrontano diverse criticità fondamentali:

Scalabilità: I metodi esatti (ad esempio, Programmazione Lineare Intera Mista o risolutori SMT) presentano spesso una complessità computazionale fattoriale o esponenziale, rendendoli impraticabili per circuiti che si avvicinano al regime dei mille qubit.
Limitazioni del Tipo di Taglio: Molte euristiche ottimizzano i tagli di fili (wire cuts) o i tagli di porte (gate cuts) in isolamento, raramente combinando entrambi all'interno di un singolo procedimento di ottimizzazione.
Consapevolezza dell'Hardware (Hardware Awareness): La maggior parte degli approcci assume partizioni hardware omogenee e trascura le specifiche caratteristiche di rumore e i vincoli di connettività dei backend quantistici eterogenei, portando a una fedeltà di esecuzione subottimale.
Compromessi (Trade-offs): Bilanciare la minimizzazione dell'overhead di campionamento con la massimizzazione della fedeltà dell'hardware (riduzione del rumore) è un problema multi-obiettivo complesso che le euristiche scalabili esistenti spesso non riescono ad affrontare congiuntamente.

Metodologia

Il documento presenta MosaiQC, un framework di ottimizzazione euristica progettato per ottimizzare congiuntamente l'overhead di campionamento, il posizionamento consapevole dell'hardware (hardware-aware placement) e i tagli misti di porte e fili, mantenendo al contempo una complessità di tempo polinomiale. Il framework opera attraverso una pipeline di ottimizzazione gerarchica a quattro stadi:

1. Rappresentazione a Grafo

Per ridurre l'overhead computazionale, il circuito quantistico e la topologia dell'hardware vengono trasformati in rappresentazioni grafiche compatte, evitando di fare affidamento su ripetute valutazioni di Grafi Aciclici Diretti (DAG).

Grafo di Connettività: Rappresenta i qubit come nodi e le porte a 2 qubit come archi, pesati dal numero di porte.
Dipendenze Temporali: Memorizzate separatamente per valutare efficientemente i tagli di fili quando le partizioni condividono qubit.
Topologia dell'Hardware: Modellata come un grafo pesato dove i pesi degli archi incorporano metriche di rumore (ad esempio, errori delle porte $1-q$ e $2-q$ ) e costi di routing (stimati tramite percorsi minimi di Floyd-Warshall).

2. Partizionamento Iniziale (Warm-Start)

Il framework utilizza la libreria METIS per eseguire un partizionamento globale del grafo. Questo passaggio genera una soluzione iniziale che soddisfa i vincoli di capacità dell'hardware, fornendo un punto di partenza di alta qualità per il successivo raffinamento. Questa fase affronta principalmente i tagli di porte o i tagli di fili singolarmente per stabilire una linea di base.

3. Raffinamento Locale

Un algoritmo di Ricerca Tabu (Tabu Search) raffina iterativamente la partizione iniziale attraverso mosse locali:

Aggiunta di nodi alle partizioni (soggetto a capacità).
Spostamento di nodi tra partizioni.
Scambio di nodi ai confini delle partizioni.
Valutazione del Taglio Misto: La funzione di costo tiene esplicitamente conto sia dei tagli di porte che di quelli di fili. L'overhead è calcolato come $Overhead = (GateCost)^g \cdot 16^w$ , dove $g$ e $w$ sono i conteggi dei tagli di porte e di fili, rispettivamente. Per ottimizzare il calcolo, viene utilizzato il logaritmo di questo costo durante la ricerca.
Strategia di Valutazione Locale: Inveve di rivalutare l'intero grafo, il framework utilizza una strategia di lookup dei tagli di fili locale basata su rappresentazioni grafiche a livello di qubit, riducendo significativamente la complessità a $O((a+1)p \log p)$ per partizioni sovrapposte.

4. Assegnazione delle Partizioni Consapevole dell'Hardware

Per ottimizzare la fedeltà di esecuzione, Mos di QC impiega un risolutore per il Problema di Assegnazione Quadratica (QAP) utilizzando l'algoritmo di Frank-Wolfe.

Obiettivo: Trovare una matrice di permutazione che mappi le partizioni del circuito ai backend hardware per massimizzare la fedeltà attesa (minimizzare il rumore).
Scoring: L'algoritmo minimizza la traccia del prodotto della matrice della partizione del circuito e della matrice della topologia del rumore dell'hardware. I pesi del rumore sono trasformati logaritmicamente ( $w = \ln(1 - \epsilon_{noise})$ ) per gestire efficacemente le diverse scale.
Funzione di Costo Adattiva: Per bilanciare il costo computazionale delle valutazioni QAP con la qualità dell'ottimizzazione, il framework utilizza una funzione di costo adattiva ( $S_{adapt}$ ) che normalizza l'overhead di taglio rispetto al punteggio di posizionamento QAP. Le valutazioni QAP vengono eseguite a intervalli stabiliti piuttosto che in ogni iterazione.

Contributi Chiave

Il documento rivendica i seguenti contributi specifici:

Framework di Ottimizzazione Congiunta: Un framework euristico che ottimizza i tagli misti di fili e porte all'interno di una singola procedura, una capacità raramente dimostrata negli strumenti scalabili esistenti.
Valutazione Locale dei Tagli di Fili: Una strategia basata su rappresentazioni grafiche a livello di qubit che riduce la complessità computazionale delle ripetute ottimizzazioni basate su DAG.
Supporto per Hardware Eterogenei: Uno strato di astrazione che supporta backend quantistici con diverse capacità di qubit e caratteristiche di rumore, consentendo partizioni hardware di dimensioni miste.
Posizionamento Consapevole dell'Hardware: Un metodo che utilizza il matching di grafi a doppio peso (risolto tramite Frank-Wolfe) per posizionare le partizioni sull'hardware, ottimizzando esplicitamente per la riduzione del rumore.
Strategia Ibrida Scalabile: Una combinazione di partizionamento globale tramite METIS per l'inizializzazione warm-start e raffinamento tramite Tabu Search, raggiungendo una complessità di tempo polinomiale $O(k \cdot n_q + m \cdot n_q^3)$ .

Risultati

Il framework è stato valutato contro l'add-on di circuit-cutting di Qiskit (utilizzando l'algoritmo di Dijkstra) e metodi di ricerca esaustiva attraverso vari benchmark (es. Adder, BV, AQFT, QAOA, VQE) e dimensioni di circuito (da 6 a 1000 qubit).

Prestazioni di Runtime: MosaiQC ha ottenuto un accoramento della velocità (speedup) della media geometrica di 2.88× nel runtime rispetto al baseline. Fondamentalmente, ha ottimizzato con successo circuiti fino a 1000 qubit, mentre il baseline spesso subiva timeout o errori di overflow di memoria.
Overhead di Campionamento: Il framework ha dimostrato una riduzione media del numero di tagli del 16,84% rispetto al baseline. Ciò ha portato a un miglioramento della media geometrica dell'overhead di campionamento di circa $5,38 \cdot 10^{11}\times$ (a causa della natura esponenziale dell'overhead).
Miglioramento della Fedeltà: La strategia di posizionamento consapevole dell'hardware ha mostrato una forte correlazione di Pearson ( $r \approx 0,83 - 0,87$ ) tra il punteggio QAP e la fedeltà misurata. Nei benchmark di fedeltà, MosaiQC ha ottenuto un miglioramento della fedeltà locale media di +19,56% ± 6,17% rispetto al baseline quando il peso del rumore è stato prioritizzato.
Convergenza: L'approccio ibrido warm-start ha ridotto significativamente il numero di iterazioni necessarie per la convergenza rispetto agli approcci di solo raffinamento, evitando che l'ottimizzatore rimanesse intrappolato in minimi locali nelle prime fasi della ricerca.

Significato e Rivendicazioni

Gli autori posizionano MosaiQC come un'evoluzione necessaria per gli strumenti di compilazione quantistica. Affermano che, man mano che i circuiti quantistici scalano verso il regime dei mille qubit, l'ottimizzazione stessa del posizionamento dei tagli non deve diventare un collo di bottiglia computazionale.

Il documento asserisce che MosaiQC dimostra un rapporto superiore tra velocità di esecuzione e qualità della soluzione, aggiungendo funzionalità fondamentali (tagli misti, supporto per hardware eterogeneo e posizionamento consapevole del rumore) che sono escluse dalla maggior parte dei competitor. Pur riconoscendo che il circuit cutting pratico rimane fondamentalmente limitato dall'esponenziale overhead di campionamento richiesto per la ricostruzione, gli autori sostengono che MosaiQC stabilisca una base pratica per il circuit cutting scalabile nei futuri sistemi di calcolo quantistico eterogenei. Il lavoro suggerisce che l'ottimizzazione euristica scalabile può ridurre sostanzialmente l'overhead computazionale del posizionamento dei tagli del circuito, consentendo l'esecuzione di algoritmi che sarebbero altrimenti impraticabili sull'attuale hardware.