Potenziale informativo: un approccio variazionale alla complessità dell’informazione quantistica

Abstract degli autori

La complessità dell’informazione quantistica (QIC), introdotta da Touchette [Touchette, STOC 2015], si è dimostrata uno dei metodi più efficaci per dimostrare risultati sulla complessità della comunicazione quantistica ed è stata anche dimostrata equivalente alla complessità della comunicazione quantistica ammortizzata. Purtroppo, in generale la QIC è difficile da analizzare perché consiste in una somma di termini di informazione mutua condizionata quantistica, difficili da stimare. In questo lavoro presentiamo un nuovo approccio variazionale, il potenziale informativo, per analizzare la QIC e dimostrare limiti inferiori alla comunicazione quantistica, ispirato alla rappresentazione del risolvente dell’entropia relativa quantistica. Questo approccio collega la QIC dei singoli messaggi a una forma quadratica, rendendo così più agevole l’analisi e consentendoci di limitare gli incrementi positivi cumulativi del potenziale nel corso di un protocollo quantistico interattivo tramite la sua QIC. I limiti inferiori alla crescita del potenziale si traducono quindi in limiti inferiori sia alla QIC sia alla complessità della comunicazione quantistica. Come applicazione, dimostriamo un limite inferiore ottimale di $Ω(1/r)$ alla QIC della funzione $\mathsf{AND}$ a due bit, nonché un limite inferiore ottimale di $Ω(n/r)$ alla complessità della comunicazione quantistica di Set-Disjointness a $r$ round, risolvendo un problema aperto in~[Braverman, Garg, Ko, Mao, Touchette FOCS 2015]. Inoltre, dimostriamo anche un teorema di somma diretta per la complessità della comunicazione quantistica di Set Disjointness con un numero limitato di round. Grazie al limite stretto sulla QIC della funzione $\mathsf{AND}$, stabiliamo inoltre un trade-off quasi ottimale per la complessità asimmetrica della comunicazione quantistica di $\mathsf{Set} \mathsf{Disjointness}$: $(q_A+1)(q_B+1)=Ω(n)$, dove $q_A$ e $q_B$ indicano il numero totale di qubit inviati rispettivamente da Alice e Bob.