⚛️ quantum physics

Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings

Questo articolo introduce un metodo basato sul simulated annealing che ottimizza la traslazione di circuiti QAOA su hardware quantistico a layout fisso, riducendo significativamente l'overhead di codifica delle catene di parità twine e delle reti SWAP, ottenendo così sostanziali diminuzioni della profondità del circuito e del numero di gate a due qubit rispetto ai traslatori standard.

Autori originali: J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

Pubblicato 2026-08-12

📖 4 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

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 organizzare una festa di danza massiccia e caotica dove ogni ospite deve tenersi per mano con tutti gli altri ospiti in un certo momento per eseguire una routine speciale. Ora, immagina che la pista da ballo sia un corridoio stretto, in fila indiana, dove le persone possono solo tenersi per mano con la persona immediatamente accanto a loro. In questo corridoio, le persone devono spostarsi, scambiarsi di posto e infilarsi tra la folla finché non diventano vicini. Questo rimescolamento richiede tempo e, ogni volta che due persone si urtano per scambiarsi di posto, c'è il rischio che possano inciampare, lasciare la presa o rovinare la coreografia. Nel mondo del calcolo quantistico, questa pista da ballo è un chip quantistico, gli ospiti sono minuscole particelle chiamate qubit, e l'"inciampare" è un tipo di errore che rovina il calcolo. Gli scienziati cercano costantemente di capire come far comunicare questi qubit tra loro in modo efficiente senza inciampare l'uno nell'altro, specialmente perché gli attuali chip sono come quel corridoio stretto e non possono connettere tutti con tutti direttamente.

Questo articolo riguarda la ricerca della migliore coreografia per quella danza. I ricercatori si sono concentrati su un algoritmo specifico chiamato QAOA, che viene utilizzato per risolvere enigmi complessi come trovare il modo migliore per dividere un gruppo di persone in due squadre. Per far sì che questo funzioni su un chip monodimensionale stretto, hanno dovuto usare la "traspilazione", che è solo un modo elegante per dire riorganizzare le istruzioni in modo che l'hardware possa comprenderle. Hanno testato due modi principali per questo rimescolamento: la "rete SWAP", che è come una danza di linea standard e organizzata in cui tutti si muovono passo dopo passo, e un metodo più recente e complicato chiamato "Parity Twine Chains" (PTC), che è più simile all'codificare le informazioni di due ballerini nelle mosse di una sola persona per risparmiare spazio. Gli autori hanno anche inventato una nuova tecnica di "simulated annealing", che è come un coach intelligente, basato su tentativi ed errori, che prova migliaia di diverse formazioni iniziali per trovare quella che richiede il minor numero di rimescolamenti.

Il team ha scoperto che per enigmi piccoli e sparsi, i programmi informatici standard utilizzati da aziende come IBM erano in realtà piuttosto bravi a minimizzare il numero di movimenti. Tuttavia, man mano che gli enigmi diventavano più grandi e le connessioni tra i qubit diventavano più frequenti, i loro nuovi metodi iniziavano a brillare. Utilizzando il loro coach intelligente per riorganizzare l'ordine iniziale dei qubit, sono riusciti a ridurre significativamente il numero di volte in cui i qubit dovevano scambiarsi di posto. Per un enorme enigma da 120 qubit con connettività al 25%, il loro metodo ha tagliato l'87% della profondità del circuito (il tempo necessario per l'esecuzione) e il 29% dei gate a due qubit (le mosse rischiose) rispetto al software standard di IBM. Hanno testato questo anche su veri computer quantistici, specificamente sui dispositivi "ibm fez" e "ibm kingston". Sul dispositivo "ibm fez", sono riusciti a trovare la soluzione perfetta per un problema da 20 qubit utilizzando il loro metodo PTC, mentre il metodo standard funzionava solo fino a 15 qubit. Interessante è che sul dispositivo "ibm kingston", il metodo SWAP standard ha effettivamente performato leggermente meglio del metodo PTC per un tipo specifico di problema, suggerendo che a volte avere meno mosse non è l'unica cosa che conta; il modo in cui l'informazione viene codificata conta altrettanto. I ricercatori suggeriscono che, sebbene il loro metodo sia uno strumento potente per ridurre gli errori e risparmiare tempo, non è una bacchetta magica che funziona perfettamente in ogni singolo scenario, e la scelta migliore dipende dalla forma specifica del problema e dalle peculiarità dell'hardware.

Sintesi Tecnica: Ottimizzazione della Transpilazione di Circuiti QAOA con Parity Twine e Codifiche SWAP Network

Problema
Gli attuali processori quantistici superconduttori (QPU) soffrono di una connettività limitata tra i qubit, tipicamente ristretta alle interazioni tra vicini prossimi su topologie specifiche (ad esempio, reticoli heavy-hex). L'esecuzione di algoritmi come il Quantum Approximate Optimization Algorithm (QAOA), che spesso richiedono interazioni a due qubit densamente connesse o completamente connesse, necessita di un processo di transpilazione. Questo processo mappa i qubit logici su qubit fisici e inserisce porte SWAP per soddisfare i vincoli di connettività. Tuttavia, le porte SWAP vengono decomposte in più porte a due qubit (ad esempio, tre CNOT), che sono la principale fonte di rumore ed errore sui dispositivi NISQ (near-term). Sebbene le codifiche strutturate come gli SWAP network e le Parity Twine Chains (PTC) offrano benefici analitici sulle risorse per grafi completamente connessi, la loro applicazione a grafi scarsamente connessi (non completamente connessi) rimane subottimale. Inoltre, trovare la mappatura iniziale ottimale dei qubit (un problema di isomorfismo di sottografo) per minimizzare il conteggio delle porte in questi scenari sparsi è un problema NP-hard, e gli attuali risolutori come SATMapper presentano limiti di scalabilità e tempi di esecuzione.

Metodologia
Gli autori propongono un approccio ibrido che combina strategie di codifica strutturata con un'euristica di simulated annealing (SA) per ottimizzare la mappatura iniziale dei qubit logici-fisici.

Codifiche:
- SWAP Network: Uno schema di routing strutturato su una catena 1D dove strati alternati di porte SWAP tra vicini prossimi spostano i qubit logici per creare le adiacenze richieste.
- Parity Twine Chains (PTC): Un metodo che codifica l'informazione Z multi-qubit in singoli qubit fisici tramite parità. Ciò consente di eseguire interazioni non locali come rotazioni locali a singolo qubit ( $R_Z$ ), riducendo il conteggio delle porte a due qubit rispetto agli SWAP network. Il metodo utilizza una strategia di decodifica in cui vengono effettuate misurazioni nella base di parità e l'elaborazione classica recupera la stringa di bit logica, evitando la necessità di ulteriori porte CNOT per tornare alla base computazionale.
Ottimizzazione tramite Simulated Annealing (SA):
- Gli autori introducono un algoritmo basato su SA per risolvere il problema dell'isomorfismo di sottografo per entrambe le codifiche SWAP e PTC.
- Funzione di Costo: La funzione di costo è combinatoria e non regolare (non-smooth), e valuta il numero di porte a due qubit che possono essere rimosse (pruned) dal circuito. Essa verifica, livello per livello, se le coppie di qubit mappate corrispondono agli archi nativi nel grafo di accoppiamento dell'hardware. Se un'interazione richiesta è assente nel grafo del problema, le corrispondenti porte nello schema di codifica vengono omesse.
- Processo: L'algoritmo scambia iterativamente coppie di etichette di qubit per trovare una permutazione che minimizzi il conteggio totale delle porte a due qubit e la profondità del circuito. Questo approccio è stato scelto perché i metodi basati sul gradiente sono inadatti allo spazio di ricerca discreto e i metodi esatti sono computazionalmente proibitivi.
Benchmarking e Modellazione del Rumore:
- Il metodo viene confrontato con i transpiler standard (Qiskit-T, Qiskit-P, Qiskit-AI, TKET) e con SATMapper.
- Le simulazioni del rumore utilizzano un modello di rumore depolarizzante che agisce sulle porte a due qubit all'interno di un protocollo Linear Ramp QAOA (LR-QAOA) per problemi di Weighted MaxCut (WMC).
- La validazione sperimentale è eseguita su dispositivi quantistici IBM (ibm_fez e ibm_kingston).

Contributi Chiave

Codifiche Ottimizzate tramite SA: L'introduzione di una strategia di simulated annealing per ottimizzare l'ordinamento iniziale dei qubit per entrambe le codifiche PTC e SWAP, mirando specificamente a grafi non completamente connessi.
Scalabilità: Dimostrare che l'approccio SA scala efficacemente a grandi numeri di qubit (fino a 200 qubit in simulazione), offrendo un vantaggio di runtime di ordini di grandezza rispetto a SATMapper pur ottenendo una qualità della soluzione comparabile.
Decodifica PTC: Una descrizione dettagliata di una strategia di decodifica per PTC che elimina la necessità di porte CNOT che aumentano la profondità del circuito per tornare alla base computazionale.
Validazione Sperimentale: La prima implementazione sperimentale della codifica PTC su hardware quantistico reale.

Risultati

Riduzione del Conteggio delle Porte e della Profondità: Per i circuiti QAOA con densità di archi ( $E_d$ $E_{d}$ ) superiori a determinate soglie, PTC+SA e SWAP+SA superano significativamente i transpiler standard.
- Per un'istanza a 120 qubit con connettività al 25%, il metodo proposto ha ottenuto una riduzione dell'87% della profondità del circuito e una riduzione del 29% delle porte a due qubit rispetto al transpiler Qiskit (livello di ottimizzazione 3).
- La soglia affinché PTC+SA superi Qiskit-T in termini di conteggio porte diminuisce all'aumentare della dimensione del sistema (da $E_d \approx 0.35$ per 20 qubit a $E_d \approx 0.13$ per 120 qubit).
Efficienza del Tempo di Esecuzione: Il metodo SA converge a soluzioni di alta qualità in pochi secondi per problemi da 200 qubit, mentre SATMapper richiede centinaia o migliaia di secondi.
Resilienza al Rumore:
- Simulazione: Nelle simulazioni del rumore, PTC ha mostrato una probabilità di successo ( $p_{gs}$ ) superiore rispetto a SWAP per livelli di rumore bassi o moderati grazie al minor numero di porte, sebbene il rapporto di approssimazione ( $r$ ) sia rimasto simile per entrambi.
- Hardware Reale (ibm_fez): La codifica PTC ha esteso l'intervallo di esperimenti LR-QAOA utili. Sono stati trovati ottimi soluzioni per problemi fino a 20 qubit usando PTC, rispetto ai soli 15 qubit con SWAP. La distinzione rispetto al campionamento casuale si è mantenuta fino a 22 qubit per PTC contro 20 per SWAP.
- Hardware Reale (ibm_kingston): Per un problema a 20 qubit con $E_d = 0.298$ , SWAP+SA ha ottenuto il miglior rapporto di approssimazione (miglioramento del 20.83% rispetto al caso casuale), superando PTC+SA (13.99%). Gli autori osservano che, sebbene PTC utilizzi meno porte, la codifica delle coppie logiche in singoli qubit fisici può essere più sensibile all'accumulo di rumore in scenari non completamente connessi.
Confronto tra Transpiler: I transpiler standard (come Qiskit-T) spesso minimizzano il conteggio delle porte a scapito di un aumento significativo della profondità del circuito, il che esacerba il rumore. I metodi proposti mantengono circuiti compatti con profondità inferiore.

Significato e Rivendicazioni
Il documento afferma di presentare la prima dimostrazione in cui le codifiche SWAP e PTC superano i metodi di transpilazione standard in scenari con ridotta connettività tra i qubit. Costituisce inoltre la prima implementazione sperimentale della codifica PTC su hardware quantistico reale.

Gli autori sottolineano che, sebbene le codifiche strutturate ottimali siano ben note per i grafi completamente connessi, la loro applicazione a grafi parzialmente connessi tramite la proposta ottimizzazione basata su SA produce riduzioni significative delle risorse. Concludono che per sistemi fino a 20 qubit, la codifica PTC migliora le prestazioni sull'hardware reale, estendendo la dimensione dei problemi praticabili per LR-QAOA. Tuttavia, notano con modestia che in esperimenti non completamente connessi su ibm_kingston, SWAP+SA ha talvolta superato PTC+SA, suggerendo che il compromesso tra conteggio delle porte e sensibilità al rumore dipenda fortemente dalla struttura della codifica e dalla topologia del problema. Il lavoro stabilisce un percorso pratico per l'esecuzione di QAOA su dispositivi near-term con vincoli di connettività e overhead ridotto.

Articoli simili