Entangled simultaneity versus classical interactivity in communication complexity

DOI10.1145/2897518.2897545MaRDI QIDQ5361887zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.05059

zbMATH Keywords

model separationquantum communication complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked, whether there existed a function with an efficient quantum one-way protocol, but still no efficient classical two-way protocol. In 2010 Klartag and Regev demonstrated such a function and asked, whether there existed a function with an efficient quantum simultaneous-messages protocol, but still no efficient classical two-way protocol. In this work we answer the latter question affirmatively and present a partial function Shape, which can be computed by a protocol sending entangled simultaneous messages of poly-logarithmic size, and whose classical two-way complexity is lower bounded by a polynomial.

Recommendations

• Simultaneous communication protocols with quantum and classical messages
• Quantum one-way communication can be exponentially stronger than classical communication
• Quantum entanglement and the communication complexity of the inner product function
• scientific article; zbMATH DE number 5568623
• Exponential separation of quantum and classical communication complexity

Cited in

(9)

• Quantum versus randomized communication complexity, with efficient players
• scientific article; zbMATH DE number 5953454 (Why is no real title available?)
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• Classical Communication and Entanglement Cost in Preparing a Class of Multi-qubit States
• Permutation Enhances Classical Communication Assisted by Entangled States
• Query-to-communication lifting for BPP
• Entangled Simultaneity Versus Classical Interactivity in Communication Complexity
• Simultaneous communication protocols with quantum and classical messages
• Quantum versus randomized communication complexity, with efficient players

This page was built for publication: Entangled simultaneity versus classical interactivity in communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361887)