2026-08-17T17:36:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18295 2024-03-06T11:01:32Z ddc:004 open_access

Trade-Offs Between Entanglement and Communication Arunachalam, Srinivasan Girish, Uma quantum communication complexity exponential separation boolean hidden matching forrelation xor lemma We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on n bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every k ≥ ~1: Q‖^* versus R2^*: We show that quantum simultaneous protocols with Θ̃(k⁵log³n) qubits of entanglement can exponentially outperform two-way randomized protocols with O(k) qubits of entanglement. This resolves an open problem from [Dmitry Gavinsky, 2008] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gavinsky, 2019; Girish et al., 2022]. R‖^* versus Q‖^*: We show that classical simultaneous protocols with Θ̃(k log n) qubits of entanglement can exponentially outperform quantum simultaneous protocols with O(k) qubits of entanglement, resolving an open question from [Gavinsky et al., 2006; Gavinsky, 2019]. The best result prior to our work was a relational separation against protocols without entanglement [Gavinsky et al., 2006]. R‖^* versus R1^*: We show that classical simultaneous protocols with Θ̃(k log n) qubits of entanglement can exponentially outperform randomized one-way protocols with O(k) qubits of entanglement. Prior to our work, only a relational separation was known [Dmitry Gavinsky, 2008]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Srinivasan Arunachalam and Uma Girish 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.25 urn:nbn:de:0030-drops-182957 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.25 eng https://creativecommons.org/licenses/by/4.0/legalcode