Sintesi Tecnica: Traspilazione Efficiente di Circuiti di Gate Commutanti su Griglie 2D

Definizione del Problema

I problemi di ottimizzazione combinatoria, come il Max-Cut (MC) e il Maximum Independent Set (MIS), sono centrali per molte applicazioni ma sono spesso NP-completi. L'Algoritmo di Ottimizzazione Approssimata Quantistica (QAOA) offre un approccio quantistico a questi problemi mappandoli in Hamiltoniane. Tuttavia, l'implementazione pratica su computer quantistici digitali affronta ostacoli significativi dovuti alla connettività limitata dell'hardware.

L'Hamiltoniana del problema $H_C$ induce tipicamente interazioni tra molte coppie di qubit. Su hardware con connettività ristretta (ad es. griglie 2D), queste interazioni non adiacenti devono essere realizzate utilizzando gate SWAP per instradare i qubit in posizioni adiacenti. Questo processo di routing aumenta la profondità del circuito e l'errore accumulato, spesso annullando i benefici degli algoritmi quantistici. Inoltre, le reti SWAP predeterminate progettate per grafi completamente connessi sono inefficienti per Hamiltoniane di costo sparse. I metodi di traspilazione standard (come quelli in Qiskit) utilizzano spesso mappature iniziali casuali e routing fissi, producendo spesso circuiti subottimali, in particolare per grafi di interazione sparsi.

Metodologia

Gli autori propongono uno schema di traspilazione specificamente progettato per circuiti composti da blocchi di gate a due qubit commutanti (tipici del QAOA) su hardware a reticolo bidimensionale (2D). La metodologia principale prevede l'alternanza tra la costruzione di sequenze di layer SWAP dipendenti dal problema e l'aggiornamento della disposizione (layout) dei qubit.

Il documento introduce e confronta diverse strategie:

1. Strategia Lineare ($S_{line}, C_{line}^{grid}$): Il baseline allo stato dell'arte dove la griglia 2D è trattata come una linea 1D. I layer SWAP alternano tra i bordi pari e dispari della linea più lunga in una griglia.
2. Strategia Ibrida ($S_{line}, C_{grid}$): Una modifica della strategia lineare che applica il routing SWAP basato sulla linea, ma sfrutta i bordi non utilizzati nella griglia 2D per applicare direttamente i gate $R_{ZZ}$ (interazioni) quando possibile, senza alterare la rete SWAP sottostante.
3. Strategia di Griglia ($S_{grid}, C_{grid}$): Una strategia che utilizza un insieme di basi personalizzato di layer SWAP ($B_{grid}$) che alterna swap orizzontali e verticali per sfruttare appieno la connettività 2D.
4. Strategia Greedy Dipendente dal Problema ($S_{greedy}, C_{grid}$): Il contributo principale degli autori. Questo metodo impiega un algoritmo di ricerca greedy per adattare la sequenza SWAP e la mappatura iniziale dei qubit al caso specifico dell'Hamiltoniana di costo del problema.
   • Ciclo Interno: Utilizza una ricerca in profondità (DFS) per esplorare un albero di configurazioni di qubit raggiungibili. Cerca il percorso più breve di layer SWAP che implementi tutte le interazioni richieste. Per gestire la complessità, la ricerca è limitata a una profondità massima $k_{max}$ prima di selezionare la migliore sequenza parziale e continuare.
   • Ciclo Esterno: Aggiorna iterativamente la mappatura iniziale dei qubit ($\pi_0$) utilizzando un risolutore di mappatura basato su SAT. Se la lunghezza della sequenza SWAP corrente supera una lunghezza di riferimento, l'algoritmo resetta la ricerca con una nuova mappatura iniziale per tentare di trovare una sequenza più breve.
   • Insieme di Basi: La ricerca utilizza un insieme di basi esteso ($B_{extended}^{grid}$) che include ulteriori layer SWAP oltre alla base standard della griglia, per scambiare l'overhead di ricerca con una riduzione della profondità del circuito.

Contributi Chiave

1. Traspilazione Dipendente dal Problema: Il documento introduce un algoritmo greedy che costruisce dinamicamente strategie SWAP e mappature iniziali su misura per il grafo di interazione specifico dell'istanza del problema, invece di fare affidamento su reti fisse e agnostiche rispetto al problema.
2. Baseline Ibrida: La proposta di una strategia ibrida che utilizza i bordi della griglia 2D per le interazioni mantenendo un backbone SWAP lineare, fungendo da baseline intermedia.
3. Analisi della Scalabilità: Dimostrazione teorica ed empirica che le strategie basate su griglia, in particolare l'approccio greedy, ottengono un miglioramento asintotico $O(\sqrt{n})$ nelle metriche di complessità del circuito (layer SWAP, profondità, conteggio dei gate) rispetto alle strategie lineari, mentre le strategie lineari scalano come $O(n)$ per grafi sparsi.
4. Validazione Hardware: Esecuzione sperimentale di circuiti QAOA su hardware a reticolo rettangolare di IBM per problemi fino a 80 qubit, validando i risultati delle simulazioni.

Risultati

Gli autori hanno testato il loro approccio su istanze MC su grafi Random Regular (RR) (grado $d=3$) e istanze MIS su grafi Erdős–Rényi (ER) (probabilità di arco $q=0.08$).

• Complessità del Circuito: Rispetto ai metodi standard (inclusa la strategia lineare e il traspilatore SABRE di Qiskit), la strategia greedy ha ridotto la profondità del circuito e il numero di gate a due qubit di circa un fattore due per i grafi sparsi.
  • Per i grafi RR, il numero di layer SWAP, la profondità e i gate CZ scalavano come $n$, $n$ e $n^2$ per le strategie lineari, mentre la strategia greedy manteneva costanti inferiori e un migliore comportamento di scalabilità.
  • Per i grafi ER, la strategia greedy ha superato significativamente le strategie lineari, con il conteggio dei gate CZ che scalava come $O(n^{5/2})$ rispetto a $O(n^3)$ per le strategie lineari.
• Regime di Fattibilità: La riduzione del conteggio dei gate ha esteso la dimensione fattibile del problema per l'hardware rumoroso. Per un budget fisso di gate CZ (ad es. 3.600 gate), la strategia greedy ha permesso l'esecuzione di istanze fino a 100 nodi, mentre la strategia lineare era limitata a circa 60 nodi.
• Rapporti di Approssimazione: Gli esperimenti hardware hanno dimostrato prestazioni migliorate:
  • Max-Cut (MC): La strategia greedy ha migliorato il rapporto di approssimazione medio fino al 6,62% (a 72 qubit) rispetto alla strategia lineare.
  • Maximum Independent Set (MIS): Il miglioramento è stato ancora più marcato, raggiungendo il 9,32% (a 56 qubit).
• Confronto sulla Troncatura: A differenza degli approcci che troncano l'Hamiltoniana di costo per ridurre la profondità (sacrificando le garanzie teoriche), la strategia greedy ha implementato un sottoinsieme significativamente più ampio di interazioni target per lo stesso numero di layer SWAP, preservando più struttura del problema.

Significato e Rivendicazioni

Il documento afferma che una traspilazione efficiente è critica per le prestazioni pratiche di QAOA sull'hardware attuale. Gli autori sostengono che il loro schema di traspilazione "problem-aware" sia fondamentale per migliorare le prestazioni degli algoritmi quantistici su dispositivi rumorosi, in particolare per problemi di ottimizzazione sparsi.

Le rivendicazioni chiave riguardanti la significatività includono:

• Abilitare Esperimenti Più Grandi: Il metodo permette esperimenti fino a 80 qubit sull'hardware attuale riducendo la profondità del circuito e l'accumulo di errori.
• Amplificare i Miglioramenti dell'Hardware: Man mano che la qualità dell'hardware migliora (aumentando il budget disponibile di gate CZ), i benefici di una traspilazione efficiente vengono amplificati. La strategia greedy consente un aumento maggiore della dimensione del problema accessibile rispetto alle strategie lineari al crescere del budget di gate.
• Rilevanza per il Vantaggio Quantistico: L'approccio è particolarmente rilevante per sondare i regimi di potenziale vantaggio quantistico, inclusi i regimi di durezza dove i solver classici faticano (ad es. istanze MIS a bassa densità con 500 nodi).
• Preparazione al Futuro: Il lavoro evidenzia come, man mano che i codici di correzione dell'errore (come il codice bivariate bicycle) richiederanno una connettività strutturata e non locale basata su reticoli rettangolari, l'adattamento delle strategie di traspilazione per sfruttare la connettività 2D sarà essenziale per ridurre la complessità dei circuiti nelle future architetture.

Gli autori concludono che, sebbene il loro metodo si basi su layer SWAP predefiniti, esso dimostra che una traspilazione "problem-aware" è un passo necessario per colmare il divario tra algoritmi quantistici teorici ed esecuzione pratica su hardware rumoroso.