Quantum one way vs. classical two way communication in XOR games

2020/03/21 by Abderramán Amr, Amr, Abderramán, Ignacio Villanueva +1 · 1 citation
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2003.09747

openalex publication_date 2020/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work we give an example of exponential separation between quantum and classical resources in the setting of XOR games assisted with communication. Specifically, we show an example of a XOR game for which O(n) bits of two way classical communication are needed in order to achieve the same value as can be attained with log n qubits of one way communication. We also find a characterization for the value of a XOR game assisted with a limited amount of two way communication in terms of tensor norms of normed spaces.

Cited by

• Composable, unconditional security without a Quantum secret key: public broadcast channels and their conceptualizations, adaptive bit transmission rates, fidelity pruning under wiretaps

Related

• Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, XOR^*, compiled XOR, XOR^*, and strong parallel repetiton of XOR, XOR^*, and FFL games
• Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
• Quantum XOR Games
• Quantum strategies are better than classical in almost any XOR game
• On the power of quantum entanglement in multipartite quantum XOR games