Bounds on oblivious multiparty quantum communication complexity
Bounds on oblivious multiparty quantum communication complexity
复制标题
多方量子通信复杂性的界限
DOI：
10.1007/978-3-031-20624-5_39
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Daiki Suruga
中科院分区：
文献类型：
--
作者：
Francois Le Gall;Daiki Suruga
The main conceptual contribution of this paper is investigating quantum multiparty communication complexity in the setting where communication isoblivious. 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 fixedindependently of the inputbefore the execution of the protocol. We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantumk-party communication complexity using lower bounds on theirtwo-partycommunication complexity. We apply this technique to prove tight lower bounds for all symmetric functions with AND gadget, and in particular obtain an optimallower bound on the oblivious quantumk-party communication complexity of then-bit Set-Disjointness function. We also show the tightness of these lower bounds by giving (nearly) matching upper bounds.
