Vantaggi quantistici ottimali e verificabili nella complessità della comunicazione

Abstract degli autori

Stabiliamo separazioni ottimali tra quantistico e classico nella complessità della comunicazione per problemi di ricerca. Introduciamo un problema di ricerca totale, chiamato Pelagic Fourier Fishing, e mostriamo che ammette un protocollo quantistico unidirezionale con $n$ qubit, mentre ogni protocollo randomizzato bidirezionale richiede $Ω(2^n)$ bit di comunicazione. Introduciamo poi una variante di questo problema le cui soluzioni possono essere verificate in tempo polinomiale. Anche questa variante ammette un protocollo quantistico unidirezionale con $n$ qubit, mentre ogni protocollo randomizzato unidirezionale richiede $Ω(2^n)$ bit di comunicazione. Costruiamo inoltre una famiglia di problemi di ricerca totali verificabili in modo efficiente che raggiunge una separazione di $n$ rispetto a $Ω_d(n^d)$ tra la comunicazione quantistica unidirezionale e quella randomizzata unidirezionale, per ogni $d \ge 2$ fissato. Nel protocollo quantistico, Alice prepara il proprio messaggio usando una singola operazione unitaria del $d$-esimo livello della gerarchia di Clifford, mentre Bob esegue una misurazione di Clifford. Questa separazione è asintoticamente ottimale sotto questo vincolo sul messaggio di Alice. Per $d = 2$, il messaggio di Alice è uno stato stabilizzatore e la misurazione di Bob è di Clifford, quindi il protocollo non usa magic, ma raggiunge comunque un vantaggio quantistico quadratico ottimale. Infine, discutiamo come queste separazioni possano essere adattate a esperimenti di vantaggio quantistico nel breve termine, nei quali il vantaggio dimostrato è sia incondizionato sia verificabile in modo efficiente.