Gate Toffoli randomizzate senza ancilla e conteggio di T degli oracoli booleani

Abstract degli autori

Nei circuiti Clifford+T fault-tolerant, un oracolo booleano richiede gate T e qubit aggiuntivi; con quattro o più qubit, ogni gate Toffoli esatto richiede un qubit aggiuntivo. Gosset, Kothari e Zhang hanno mostrato che campionare un nuovo circuito casuale a ogni chiamata rende il conteggio di T del gate Toffoli indipendente dalla sua dimensione, ma un’implementazione diretta del loro campionatore usa circa un qubit aggiuntivo per ogni bit di precisione. Mostriamo che calcolare sul posto le parità campionate usando i controlli del gate stesso elimina tutti i qubit aggiuntivi quando il gate è sufficientemente grande: ogni circuito casuale usa quindi circa 8 gate T per bit di precisione e prende in prestito soltanto gli ingressi inattivi del gate stesso. Si tratta di un gate T in più per circuito rispetto alla migliore variante senza misurazioni, che mantiene un’ancilla pulita. Lo stesso vale per gli XOR di funzioni indicatrici di sottospazi affini, come i test di uguaglianza e le verifiche di equazioni lineari. Per i circuiti randomizzati che non effettuano misurazioni, questo risultato è entro un fattore otto dall’ottimo, a meno di una costante additiva, anche in presenza di qubit aggiuntivi; inoltre, quando ogni circuito casuale calcola esattamente una funzione booleana, colmare asintoticamente il divario equivale a determinare la costante principale nel conteggio di T dei gate Toffoli esatti con più controlli. Infine, l’oracolo della funzione indicatrice di un insieme casuale a densità fissata richiede un numero esponenziale di gate T a errore costante, mentre quello di un sottospazio affine della stessa densità ne richiede un numero costante; i qubit aggiuntivi riducono il costo esponenziale soltanto in modo quadratico.