Sulle dimostrazioni interattive quantistiche con un prover laconico

Abstract degli autori

I sistemi di dimostrazione interattiva con un prover laconico, studiati da Goldreich, Vadhan e Wigderson (CC, 2002), comprendono problemi verificabili con una comunicazione logaritmica del prover nel contesto classico. Negli analoghi quantistici a due messaggi, persino una risposta del prover di un solo bit comprende lo zero-knowledge statistico quantistico ($\sf QSZK$), introdotto da Watrous (FOCS 2002). Tuttavia, se si limita la domanda del verificatore a monete pubbliche classiche, la classe corrispondente collassa in $\sf BQP$, come mostrato da Beigi, Shor e Watrous (ToC, 2011). Studiamo inoltre i sistemi di dimostrazione interattiva quantistica a due messaggi con un prover laconico. A tal fine, introduciamo la classe ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, dove $\ell$ è la lunghezza della risposta del prover, e dimostriamo quanto segue: 1. Una caratterizzazione completa naturale di ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ in termini di distinguibilità di stati multipli. In particolare, la distinguibilità di stati quantistici (QSD) è completa per ${\sf QIP}_{\rm bit}$. Poiché QSD è $\sf QSZK$-difficile, il nostro risultato colloca ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, per $\ell\geq 2$, in un panorama «appena al di sopra» di $\sf QSZK$. 2. Regimi semplici in cui ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ collassa in $\sf QSZK$. Dimostriamo che QSD$[a,b]$ (e quindi ${\sf QIP}_{\rm bit}[a,b]$) appartiene a $\sf QSZK$ quando $a(n)-b(n)\geq 1/O(\log n)$, e combiniamo questo risultato con una compressione della risposta da ${\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]$ a ${\sf QIP}_{\rm bit}$ per ottenere un altro regime semplice quando $2c>(1+2^{\ell/2})s$. È notevole che la nostra polarizzazione migliorata si applichi a SD e $\sf SZK$, risolvendo un problema aperto in Sahai e Vadhan (JACM, 2003). 3. Anche le monete pubbliche quantistiche rendono inutile l’interazione: ${\sf qc}\text{-}{\sf QAM}[O(\sqrt{\log{n}})]$ con gap costante appartiene a $\sf BQP$, dove ${\sf qc}\text{-}{\sf QAM}[\ell]$ è una sottoclasse di ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ in cui la domanda del verificatore è costituita esattamente dalle metà delle coppie EPR.