Quantum Circuit Synthesis Using an Exact T Library

Riepilogo Tecnico: Sintesi di Circuiti Quantistici Utilizzando una Libreria Esatta T

Enunciato del Problema
Nel calcolo quantistico tollerante ai guasti (FTQC), l'esecuzione di porte non-Clifford, in particolare le porte T, domina il costo spazio-temporale a causa dell'overhead derivante dalla distillazione e dall'iniezione di stati magici. Mentre le porte Clifford possono essere eseguite trasversalmente con overhead trascurabile, le porte T richiedono una costosa coltivazione di stati. Di conseguenza, la minimizzazione del conteggio T è critica per le applicazioni pratiche.

I flussi di sintesi esistenti mappano tipicamente le funzioni booleane su una base $\{XOR, AND, NOT\}$ (XAG) e minimizzano il numero di porte AND come proxy per il conteggio T. Questo approccio si basa sulla Complessità Moltiplicativa (MC), che misura la non linearità classica. Tuttavia, l'articolo sostiene che la MC è un proxy inaccurato per il costo quantistico T perché non tiene conto delle cancellazioni di fase e delle semplificazioni strutturali uniche ai circuiti quantistici (ad esempio, le porte Hadamard che bloccano le ottimizzazioni T). Di conseguenza, i flussi convenzionali producono spesso circuiti subottimali in cui le opportunità strutturali perse non possono essere recuperate da ottimizzazioni post-mappatura.

Metodologia
Gli autori propongono un framework di sintesi che ottimizza direttamente il conteggio T esatto invece di utilizzare la MC come proxy. La metodologia consta di tre componenti principali:

1. Canonicalizzazione Equivalente a Clifford:
   L'articolo introduce una forma canonica per le funzioni bilineari sotto equivalenza Clifford. A differenza della MC classica, che utilizza un tensore di moltiplicazione per rappresentare gli accoppiamenti ingresso-uscita, gli autori utilizzano un tensore polinomiale di fase. Questo tensore cattura gli accoppiamenti di triplice parità tra tutti i fili (ingressi e uscite) in un contesto reversibile. Questa formulazione rivela che le operazioni quantistiche possono intrecciare ingressi e uscite, creando interazioni del terzo ordine che permettono "scorciatoie" nella decomposizione, portando a un costo T inferiore rispetto alle stime della MC classica.

2. Sintesi della Libreria Esatta T:
   Gli autori formulano il problema della sintesi T esatta come un problema di programmazione intera vincolata.

   • Input: Una funzione bilineare $f$ con $n$ ingressi e $m$ uscite, mappata su $N = n+m$ qubit.
   • Vincoli: Il problema cerca un vettore di selezione $s$ di candidati T (termini di parità) tali che il loro polinomio di fase combinato sia uguale al polinomio di fase della funzione target modulo 2.
   • Ottimizzazione: L'obiettivo è minimizzare la cardinalità di $s$ (il conteggio T).
   • Condizioni "Don't-Care": La formulazione sfrutta i qubit ancilla "puliti" (inizializzati a $|0\rangle$) come condizioni don't-care. Le fasi su questi stati ancilla sono inosservabili, permettendo riscritture Clifford a costo zero (ad esempio, sostituire combinazioni T specifiche con porte S gratuite) per ridurre ulteriormente il conteggio T.
   • Algoritmo: Un algoritmo efficiente di sintesi della libreria precalcola la matrice di mappatura e una base dello spazio nullo. Utilizza una ricerca accelerata da CUDA per trovare soluzioni esatte per funzioni con fino a sette variabili ($N \le 7$) e soluzioni subottimali per input più grandi.

3. Mappatura della Libreria Personalizzata:
   Per sfruttare appieno la libreria T esatta, gli autori hanno sviluppato un mappatore personalizzato che si integra con il flusso XAG.

   • Enumerazione dei Tagli Bilineari: Il mappatore dà priorità ai tagli che rivelano strutture bilineari (termini di grado 2 nella Forma Normale Algebrica). Potra i tagli che introdurrebbero monomi di grado 3 o superiore, non supportati dalla libreria.
   • Modello di Costo: Invece di stimare il costo tramite il conteggio AND, il mappatore interroga la libreria T Esatta precalcolata per recuperare il costo T preciso per ogni taglio valido.
   • Programmazione Dinamica: Il mappatore esegue una programmazione dinamica standard orientata all'area sui tagli, ma utilizza i punteggi T esatti per selezionare le implementazioni, preservando la struttura sottostante della rete logica.

Contributi Chiave

• Formulazione T Esatta: Un passaggio dalla minimizzazione dei conteggi AND (MC) alla minimizzazione dei conteggi T esatti, canonizzando le funzioni booleane sotto equivalenza Clifford utilizzando tensori polinomiali di fase.
• Libreria Precalcolata: Una libreria di implementazioni ottimali per T per funzioni bilineari con fino a sette variabili, sintetizzata utilizzando un approccio di programmazione intera che tiene conto delle condizioni don't-care degli ancilla puliti.
• Mappatore Personalizzato: Un algoritmo di mappatura che preserva esplicitamente le strutture bilineari durante l'enumerazione e la classificazione dei tagli, utilizzando la libreria T esatta per guidare le decisioni di ottimizzazione.

Risultati Sperimentali
Gli autori hanno valutato il loro approccio su diverse famiglie di benchmark, inclusi benchmark aritmetici EPFL, oracoli QLUT casuali, esponenziazione modulare (algoritmo di Shor) e moltiplicatori GF($2^n$) per AES.

• Benchmark EPFL: Rispetto ai flussi di mappatura XAG precedenti guidati dalla MC esatta, il metodo proposto ha raggiunto una riduzione fino al 14,3% nel conteggio T sui benchmark aritmetici (ad esempio, moltiplicatori). La riduzione geometrica media sui benchmark è stata del 5,3%.
• Moduli Crittografici: Quando integrato in un flusso di sintesi completo (inclusa la resintesi), l'approccio ha ridotto i conteggi T meglio noti per diversi moduli crittografici fino al 40%.
• Confronto con lo Stato dell'Arte: Il metodo ha superato le ottimizzazioni T autonome come AlphaTensor e FastTODD, nonché le implementazioni QROM e SelectSwap esistenti, in particolare negli scenari con alta struttura bilineare.
• Overhead di Tempo di Esecuzione: Il calcolo aggiuntivo introdotto dalla ricerca nella libreria T esatta e dalla mappatura personalizzata ha rappresentato al massimo l'11,7% del tempo di esecuzione totale, che gli autori notano essere un costo una tantum ammortizzato sul riutilizzo dei progetti di moduli quantistici.

Significato
L'articolo afferma che assumere una trasformazione uniforme delle porte AND in un numero fisso di porte T porta a una perdita irreversibile di ottimalità. Preservando la struttura XAG mentre si ragiona con costi T esatti, l'approccio proposto produce miglioramenti tangibili nella qualità del circuito. Il lavoro dimostra che l'ottimizzazione diretta del conteggio T, facilitata da una forma canonica equivalente a Clifford e da un mappatore personalizzato, può ridurre significativamente l'overhead delle risorse per le applicazioni quantistiche tolleranti ai guasti, superando i limiti dei proxy di non linearità classica.