Bounds on oblivious multiparty quantum communication complexity

DOI10.1007/978-3-031-20624-5_39MaRDI QIDQ6164004zbMATH OpenOpenAlexFDO

Authors François Le Gall, Daiki Suruga

Publication date 26 July 2023

Published in LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

multiparty communicationquantum communication complexityquantum complexity theory

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Abstract: The main conceptual contribution of this paper is investigating quantum multiparty communication complexity in the setting where communication is emph{oblivious}. This requirement, which to our knowledge is satisfied by all quantum multiparty protocols in the literature, means that the communication pattern, and in particular the amount of communication exchanged between each pair of players at each round is fixed emph{independently of the input} before the execution of the protocol. We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantum $k$-party communication complexity using lower bounds on their emph{two-party} communication complexity. We apply this technique to prove tight lower bounds for all symmetric functions with extsf{AND} gadget, and in particular obtain an optimal $Omega(ksqrtn)$ lower bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function. We also show the tightness of these lower bounds by giving (nearly) matching upper bounds.

Cites work

• Communication complexities of symmetric XOR functions
• Communication Complexity
• Communication Complexity
• Compact oblivious routing
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 1406113 (Why is no real title available?)
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• Multi-party Quantum Communication Complexity with Routed Messages
• Multiparty quantum communication complexity of triangle finding
• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• On the distributional complexity of disjointness
• Online algorithms. The state of the art
• Quantum communication complexity of symmetric predicates
• Quantum information complexity
• Quantum search of spatial regions
• The communication complexity of distributed task allocation
• The pattern matrix method
• The Probabilistic Communication Complexity of Set Intersection

Cited in

(5)

• Optimal bounds for semi-honest quantum oblivious transfer
• Lower bounds for quantum oblivious transfer
• Multi-party Quantum Communication Complexity with Routed Messages
• scientific article; zbMATH DE number 7561499 (Why is no real title available?)
• Quantum Multiparty Communication Complexity and Circuit Lower Bounds

This page was built for publication: Bounds on oblivious multiparty quantum communication complexity

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