Progetti robusti di sottospazi e il potere di un unico piccolo testimone quantistico

Abstract degli autori

Il concetto di design di sottospazi è stato introdotto da Guruswami e Xing (STOC’13), mentre costruzioni esplicite sono state presentate da Guruswami e Kopparty (FOCS’13). Si tratta di famiglie di sottospazi la cui intersezione con un qualsiasi sottospazio dato di dimensione fissata è piccola. Introduciamo i \emph{design robusti di sottospazi}. In termini informali, sono un’estensione quantitativa in cui richiediamo che non troppi sottospazi della famiglia contengano direzioni vicine a un qualsiasi sottospazio dato di dimensione fissata. Presentiamo una costruzione probabilistica di un design robusto di sottospazi di taglia polinomiale, nonché una costruzione esplicita non banale di taglia superpolinomiale. La principale applicazione di questo nuovo concetto è una variante quantistica a spazio limitato del teorema di Valiant-Vazirani (Theor.Comput.Sci.’86), secondo cui restringere i problemi $\mathsf{NP}$-completi a istanze con al massimo un testimone accettante preserva la durezza sotto riduzioni randomizzate. Nel caso dei testimoni quantistici, la quantità analoga è la dimensione del sottospazio dei testimoni accettanti. Usiamo la nostra costruzione probabilistica di design robusti di sottospazi per isolare un testimone unico per protocolli quantistici Merlin-Arthur a spazio limitato, con completezza perfetta e un divario di accettazione al di fuori del loro sottospazio di accettazione perfetta. Come ulteriore applicazione, presentiamo una riduzione randomizzata dal test di nullità ben condizionato a protocolli quantistici Merlin-Arthur a spazio limitato con completezza perfetta. Usando un’idea analoga, mostriamo che i design ordinari di sottospazi permettono di recuperare l’inclusione classica $\mathsf{C_= L}$ di Allender, Beals e Ogihara (STOC’96) per il test di nullità generale, con una dimostrazione più semplice.