QMA(2) con entanglement condiviso limitato

Abstract degli autori

In $\mathsf{QMA}(2)$, due dimostratori senza limiti computazionali presentano testimoni quantistici non entangled a un verificatore quantistico che opera in tempo polinomiale. Ci chiediamo se consentire un entanglement condiviso limitato tra i due dimostratori cambi la potenza di $\mathsf{QMA}(2)$. A questo scopo, formalizziamo $\mathsf{QMA}(2;h)$, una variante in cui i dimostratori condividono inizialmente $h$ coppie EPR, come suggerito da Aaronson, Beigi, Drucker, Fefferman e Shor (ToC~2009). Mostriamo che un numero polinomiale di coppie EPR condivise non dà ai dimostratori alcun vantaggio nel barare: $\mathsf{QMA}(2)\subseteq\mathsf{QMA}(2;h)$ per $h=\operatorname{poly}(n)$. Con un numero logaritmico di coppie, la potenza di $\mathsf{QMA}(2)$ resta invariata, rafforzando questa inclusione a $\mathsf{QMA}(2)=\mathsf{QMA}(2;h)$ per $h=O(\log n)$. Infine, introduciamo una variante che consente anche la comunicazione classica tra i dimostratori durante la preparazione dei testimoni. Questo contesto è particolarmente rivelatore per i testimoni di dimensione logaritmica: assumendo $\mathsf{NP}\nsubseteq\mathsf{BQP}$, mostriamo che un numero superlogaritmico di coppie EPR condivise riduce strettamente la potenza computazionale del modello.