Una legge di scambio tra memoria e magia nella compilazione streaming di Clifford+T

Abstract degli autori

Una fase che raggiunge un processore fault-tolerant in componenti additive può essere conservata in memoria fino all’arrivo dell’ultimo componente, oppure eseguita man mano che arriva: la prima opzione richiede memoria classica mantenuta tra i round, la seconda magic state impegnati prima che la fase sia nota. Determiniamo il tasso di scambio $α$, ossia il numero di gate $T$ impegnati per bit di memoria sacrificata, per la compilazione coordinata per coordinata di Clifford+$T$ senza ancilla. Il limite di Ramanujan dà $α\ge2$ con costanti esplicite: è la barriera della radice quadrata imposta dal metodo spettrale. Un metodo elementare basato sui determinanti, che sfrutta il fatto che i numeratori quaternionici giacciono su sfere in entrambi gli embedding reali di $\mathbb{Q}(\sqrt2)$, conta le parole vicine a qualsiasi coset di rotazione al di sotto di tale barriera. Insieme a una dicotomia sulle altezze delle sezioni sferiche che produce e a una fibrazione sulle proiezioni razionali, il metodo garantisce ogni $α<5/2$ senza condizioni e uniformemente rispetto ai frame, grazie a una verifica SMT esatta della sua analisi per casi continui; $5/2$ è il limite di questo metodo. Per i coset con frame di Clifford, la legge del volume vale a meno di fattori subesponenziali: tutte le rotazioni attorno all’asse $z$, tranne una frazione che tende a zero, richiedono un conteggio di $T$ pari a $(3-o(1))\log_2(1/\varepsilon)$, e i processi le cui componenti impegnate sono vicine a rotazioni attorno all’asse $z$ con frame di Clifford, comprese le pipeline per rotazione, hanno $α\ge3-o(1)$; una famiglia a passthrough frazionario raggiunge questo risultato sotto l’ipotesi del costo tipico di Ross-Selinger. Sotto una congettura di equidistribuzione sostenuta da un’enumerazione esaustiva fino al conteggio di $T$ pari a 22, in generale $α=3$ e la memoria dovrebbe essere liberata per rotazioni intere. I limiti valgono anche quando le fasi si annullano a vicenda fino a dare l’identità; l’informazione laterale entra attraverso un’entropia condizionata; il mixing probabilistico dimezza i costi ma non il tasso. Con ancilla pulite e un catalizzatore a gradiente di fase, le consultazioni di tabelle raggruppate per coordinate portano il tasso a $O(1/\log\log(1/\varepsilon))$, perciò la legge del tasso costante è specifica della sintesi coordinata per coordinata.