Quantum circuit partition as a maze: emerging percolation transition via path finding

Sintesi Tecnica: Il Partizionamento di un Circuito Quantistico come Labirinto: Emergente Transizione di Percolazione tramite Ricerca di Percorsi

Definizione del Problema
Nell'ottimizzazione dei circuiti quantistici, in particolare per i dispositivi NISQ (Noisy Intermediate-Scale Quantum), la riduzione del numero di gate a due qubit (tipicamente i CNOT) è un obiettivo primario a causa del loro significativo impatto sul rumore. Sebbene il partizionamento dei circuiti permetta l'ottimizzazione parallela su più dispositivi, gli approcci esistenti spesso si basano sulla suddivisione dei gate CNOT tramite misurazioni a metà circuito e reset dei qubit. Esiste una lacuna critica nel determinare se un circuito possa essere partizionato in modo ottimale in due sottocircuiti senza tagliare alcun gate CNOT. La sfida consiste nell'identificare un criterio che distingua i circuiti partizionabili (che consentono la risintesi indipendente dei sottocircuiti) da quelli non partizionabili, senza ricorrere al taglio dei gate.

Metodologia
Gli autori formalizzano il problema del partizionamento del circuito come un compito di ricerca di un percorso all'interno di un "labirinto". La metodologia procede attraverso diverse fasi chiave:

1. Rappresentazione del Circuito:

   • Rappresentazione dei Fili (Wire Representation, $W$): Una griglia dove le righe corrispondono ai fili dei qubit e le colonne ai gate CNOT. Una cella è marcata se un CNOT coinvolge quel qubit.
   • Rappresentazione del Labirinto (Maze Representation, $M$): Una griglia trasformata dove le righe rappresentano gli spazi tra i fili dei qubit (più un padding) e le colonne alternano spazio vuoto e gate CNOT. In questa rappresentazione, i gate CNOT agiscono come "pareti". Un partizionamento valido corrisponde a un percorso continuo dal bordo sinistro al bordo destro del labirinto che non interseca queste pareti.

2. Ottimizzazione dell'Ordine dei Qubit (Simulated Annealing):

   • I circuiti generati casualmente presentano inizialmente una distribuzione delle pareti centrata nel mezzo del labirinto, rendendo difficile la traversata orizzontale.
   • Gli autori utilizzano il Simulated Annealing (SA) per permutare l'ordine dei fili dei qubit nella rappresentazione dei fili. Questa permutazione viene mappata nuovamente nella rappresentazione del labirinto.
   • Una funzione di costo viene minimizzata durante il SA, la quale penalizza le interazioni CNOT che attraversano la regione centrale della griglia. L'obiettivo è spingere le interazioni verso i confini superiore e inferiore, creando un "corridoio centrale" privo di pareti.

3. Eurisitica di Ricerca del Percorso:

   • Una volta ottimizzato il labirinto, un agente euristico attraversa il labirinto. Due agenti deterministici (uno che si muove verso l'alto quando incontra una parete, uno verso il basso) vengono lanciati da ogni cella della prima colonna.
   • Gli agenti sono vincolati a muoversi in modo monotono (senza mai tornare indietro nel tempo o invertire la direzione verticale) per garantire che i sottocircuiti risultanti siano cronologicamente coerenti.
   • Una funzione di costo pesata ($L_{tot}$) valuta i percorsi candidati basandosi su tre metrici: lo squilibrio dei CNOT tra le partizioni, lo squilibrio delle celle (area) e la deviazione della lunghezza del percorso dalla traiettoria orizzontale ideale.

4. Analisi della Scienza delle Reti:

   • Gli autori analizzano il circuito come un grafo diretto dove i nodi rappresentano gli eventi CNOT e gli archi rappresentano relazioni causali o di entanglement.
   • Utilizzano misure di centralità (grado e betweenness) e dinamiche di consenso (modello DeGroot) per quantificare la separazione delle regioni dei qubit e la miscelazione del flusso di informazioni prima e dopo l'ottimizzazione SA.

Risultati Chiave

• Transizione di Fase di Percolazione: Lo studio identifica una transizione di fase nello spazio dei circuiti quantistici. Esiste un regime distinto in cui esiste un percorso di partizionamento valido e bilanciato (partizionabile) e un regime in cui non esiste un tale percorso senza tagliare i CNOT (non partizionabile).
• Criterio di Scalabilità: La transizione è governata dal rapporto tra il numero di gate CNOT ($N_c$) e il numero di qubit ($N_q$). Gli autori osservano che il partizionamento in due cluster di CNOT bilanciati è fattibile quando $N_c$ è approssimativamente uguale a $N_q$. Man mano che la densità dei CNOT aumenta rispetto ai qubit, il "corridoio centrale" si chiude e il circuito diventa non partizionabile.
• Effetto del Simulated Annealing: Il SA ristruttura con successo il layout del circuito, spostando le interazioni CNOT verso la periferia e creando un corridoio centrale a bassa densità. Questa trasformazione sposta il profilo della distribuzione delle pareti da un profilo a picco singolo (distribuzione Beta) a un profilo bimodale, facilitando l'esistenza di un taglio orizzontale.
• Dinamica di Rete: L'analisi della centralità mostra che, nel regime partizionabile, il SA concentra le interazioni sui qubit ai bordi del registro, lasciando il centro debolmente accoppiato. Le dinamiche di consenso confermano che, nei regimi sparsi, il circuito si separa in due cluster debolmente accoppiati, mentre nei regimi densi, l'informazione si mescola globalmente, impedendo la separazione.
• Tre Regimi: L'analisi rivela tre fasi distinte basate sul punteggio di ricerca del percorso:
  1. Prima Fase (Partizionabile): Esiste un taglio strettamente orizzontale, che bilancia CNOT e celle.
  2. Regime Transiente: Il percorso deve alternare passi verticali e orizzontali per navigare tra le pareti, risultando in partizioni meno bilanciate.
  3. Seconda Fase (Non Partizionabile): Non esiste un taglio valido che separi il circuito; l'agente è costretto verso i confini, lasciando una partizione trascurabile e l'altra che contiene quasi l'intero circuito.

Significato e Rivendicazioni
Il documento sostiene di fornire un quadro teorico e numerico per comprendere il partizionamento dei circuiti come un fenomeno di percolazione. Mappando il problema come un labirinto, gli autori stabiliscono un criterio scalabile e pratico per identificare se un circuito quantistico può essere partizionato senza tagliare i gate CNOT.

Il lavoro posiziona la capacità di partizionare un circuito senza tagliare i gate di entanglement come la prima fase di una transizione di percolazione, collegando l'ottimizzazione dei circuiti quantistici a fenomeni critici più ampi, come le transizioni di fase indotte dalla misurazione e le transizioni topologiche. Gli autori affermano che il loro quadro costituisce la base per lo sviluppo algoritmico nell'ottimizzazione dei circuiti quantistici, offrendo un metodo per determinare la fattibilità della parallelizzazione dei compiti di ottimizzazione su più dispositivi senza l'overhead delle misurazioni a metà circuito. I risultati suggeriscono che per i circuiti in cui il numero di gate di entanglement scala linearmente con il numero di qubit, tale partizionamento è teoricamente possibile e può essere identificato tramite il criterio di percolazione proposto.