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 条
  • [1] Quantum multiparty communication complexity and circuit lower bounds
    Kerenidis, Iordanis
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2007, 4484 : 306 - 317
  • [2] Lower bounds on quantum multiparty communication complexity
    Lee, Troy
    Schechtman, Gideon
    Shraibman, Adi
    PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, 2009, : 254 - +
  • [3] Lower bounds on the multiparty communication complexity
    Duris, P
    Rolim, JDP
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1998, 56 (01) : 90 - 95
  • [4] Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness
    Rao, Anup
    Yehudayoff, Amir
    30TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2015), 2015, 33 : 88 - 101
  • [5] Hadamard tensors and lower bounds on multiparty communication complexity
    Ford, Jeff
    Gal, Anna
    COMPUTATIONAL COMPLEXITY, 2013, 22 (03) : 595 - 622
  • [6] Hadamard tensors and lower bounds on multiparty communication complexity
    Jeff Ford
    Anna Gál
    computational complexity, 2013, 22 : 595 - 622
  • [7] Hadamard tensors and lower bounds on multiparty communication complexity
    Ford, J
    Gál, A
    AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2005, 3580 : 1163 - 1175
  • [8] Lower bounds for quantum communication complexity
    Klauck, H
    42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2001, : 288 - 297
  • [9] Lower bounds for quantum communication complexity
    Klauck, Hartmut
    SIAM JOURNAL ON COMPUTING, 2007, 37 (01) : 20 - 46
  • [10] Communication complexity towards lower bounds on circuit depth
    Edmonds, J
    Impagliazzo, R
    Rudich, S
    Sgall, J
    COMPUTATIONAL COMPLEXITY, 2001, 10 (03) : 210 - 246