L’interazione quantistica può superattivare la possibilità di barare nella ripetizione parallela

Abstract degli autori

Studiamo i giochi interattivi con più dimostratori e i protocolli a molti round in cui la comunicazione tra il verificatore e i dimostratori è quantistica. È noto che la ripetizione parallela può ridurre l’errore di soundness dei giochi classici a due dimostratori a valori arbitrariamente vicini a zero, come mostrato da Raz (STOC ’95), anche in presenza di strategie quantistiche, come mostrato da Yuen (ICALP ’16) e da Bavarian, Vidick e Yuen (STOC ’17). Mostriamo tuttavia che la comunicazione quantistica può avere l’effetto opposto, e inaspettato. In particolare, presentiamo un gioco quantistico a un round e protocolli $\mathsf{QMIP}$ a due round il cui valore locale (senza entanglement) è strettamente minore di uno per una singola istanza, ma diventa uno con la ripetizione parallela $n$-volte per ogni $n \geq 2$. Il punto fondamentale è che la ripetizione parallela non impone soltanto ulteriori condizioni di vittoria, ma fornisce anche ulteriori risorse quantistiche: l’entanglement negli stati scambiati può infatti essere sfruttato congiuntamente tra le diverse copie. I nostri esempi a più round si basano sulla superattivazione delle capacità a errore zero dei canali quantistici. Per stabilire questo collegamento, introduciamo giochi quantistici e protocolli interattivi che caratterizzano le capacità classiche e quantistiche a errore zero a singolo uso, sia con assistenza dell’entanglement sia senza. Le nostre costruzioni utilizzano la verifica di stati quantistici e una riduzione basata sulla teleportazione da due round a uno. Al contrario, mostriamo che, quando è consentito l’entanglement condiviso, la ripetizione parallela non può aumentare il valore con entanglement se vengono scambiati al massimo $3$ messaggi; questo è in linea con i risultati classici di Bellare, Impagliazzo e Naor (FOCS ’97) e con quello sui sistemi a un solo dimostratore di Kitaev e Watrous (STOC ’00). Combinando questa monotonicità con la corrispondenza tra giochi quantistici e canali, mostriamo che le capacità classiche e quantistiche a errore zero assistite dall’entanglement non possono essere superattivate.