Quantum multiparty communication complexity and circuit lower bounds

被引:1
|
作者
Kerenidis, Iordanis [1 ]
机构
[1] LRI Univ Paris 11, CNRS, Paris, France
关键词
PROTOCOLS;
D O I
10.1017/S0960129508007263
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We define a quantum model for multiparty communication complexity and prove a simulation theorem between the classical and quantum models. As a result, we show that if the quantum k-party communication complexity of a function f is Omega(n/2(k)), its classical k-party communication is Omega(n/2(k/2)). Finding such an f would allow us to prove strong classical lower bounds for k >= log n players and make progress towards solving a major open question about symmetric circuits.
引用
收藏
页码:119 / 132
页数:14
相关论文
共 50 条
  • [41] PROPERTY TESTING LOWER BOUNDS VIA COMMUNICATION COMPLEXITY
    Blais, Eric
    Brody, Joshua
    Matulef, Kevin
    COMPUTATIONAL COMPLEXITY, 2012, 21 (02) : 311 - 358
  • [43] Property Testing Lower Bounds via Communication Complexity
    Eric Blais
    Joshua Brody
    Kevin Matulef
    computational complexity, 2012, 21 : 311 - 358
  • [44] Entropy lower bounds for quantum decision tree complexity
    Shi, YY
    INFORMATION PROCESSING LETTERS, 2002, 81 (01) : 23 - 27
  • [45] Quantum learning algorithms imply circuit lower bounds
    Arunachalam, Srinivasan
    Grilo, Alex B.
    Gur, Tom
    Oliveira, Igor C.
    Sundaram, Aarthi
    Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2022, 2022-February : 562 - 573
  • [46] Quantum learning algorithms imply circuit lower bounds
    Arunachalam, Srinivasan
    Grilo, Alex B.
    Gur, Tom
    Oliveira, Igor C.
    Sundaram, Aarthi
    2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021), 2022, : 562 - 573
  • [47] Communication Complexity Lower Bounds in Distributed Message-Passing
    Oshman, Rotem
    STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, SIROCCO 2014, 2014, 8576 : 14 - 17
  • [48] LOWER BOUNDS ON COMMUNICATION COMPLEXITY IN DISTRIBUTED COMPUTER NETWORKS.
    Tiwari, Prasoon
    1600, (34):
  • [49] Communication complexity and lower bounds on multilective computations (Extended abstract)
    Hromkovic, J
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1998, 1998, 1450 : 789 - 797
  • [50] LOWER BOUNDS ON THRESHOLD AND RELATED CIRCUITS VIA COMMUNICATION COMPLEXITY
    ROYCHOWDHURY, VP
    ORLITSKY, A
    SIU, KY
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1994, 40 (02) : 467 - 474